Loading...
Please wait, while we are loading the content...
Similar Documents
G-automata, counter languages and the Chomsky hierarchy
| Content Provider | Scilit |
|---|---|
| Author | Elder, Murray |
| Copyright Year | 2007 |
| Description | We consider how the languages of G-automata compare with other formal language classes. We prove that if the word problem of G is accepted by a machine in the class then the language of any G-automaton is in the class. It follows that the so called counter languages (languages of ℤn -automata) are context-sensitive, and further that counter languages are indexed if and only if the word problem for ℤn is indexed. AMS Classification: 20F65, 20F10, 68Q45 Keywords: G-automaton; counter language; word problem for groups; Chomsky hierarchy Introduction In this article we compare the languages of G-automata, which include the set of counter languages, with the formal language classes of context-sensitive, indexed, context-free and regular. We prove in Theorem 6 that if the word problem of G is accepted by a machine in the class M then the language of any G-automaton is in the class M. It follows that the counter languages (languages of ℤn -automata) are context-sensitive. Moreover it follows that counter languages are indexed if and only if the word problem for ℤn is indexed. The article is organized as follows. In Section 2 we define G-automata, linearly bounded automata, nested stack, stack, and pushdown automata, and the word problem for a finitely generated group. In Section 3 we prove the main theorem, and give the corollary that counter languages are indexed if and only if the word problem for ℤ n is indexed for all n. |
| Related Links | http://arxiv.org/pdf/math/0508166 |
| Ending Page | 318 |
| Page Count | 6 |
| Starting Page | 313 |
| DOI | 10.1017/cbo9780511721212.023 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2007-01-04 |
| Access Restriction | Open |
| Subject Keyword | Groups St Andrews 2005 Counter Languages Language Classes Word Problem |
| Content Type | Text |
| Resource Type | Article |
