- Title
- G-automata, counter languages and the Chomsky hierarchy
- Creator
- Elder, Murray
- Relation
- Groups St Andrews 2005. Groups St Andrews 2005, Volume 1 (St Andrews, Scotland 30 July - 6 August, 2005) p. 313-318
- Publisher Link
- http://dx.doi.org/10.1017/CBO9780511721212.023
- Publisher
- Cambridge University Press
- Resource Type
- conference paper
- Date
- 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 ℤⁿ-automata) are context-sensitive, and further that counter languages are indexed if and only if the word problem for ℤⁿ is indexed.
- Subject
- G-automaton; counter language; word problem for groups; Chomsky hierarchy
- Identifier
- http://hdl.handle.net/1959.13/931353
- Identifier
- uon:11038
- Identifier
- ISBN:9780521694698
- Language
- eng
- Full Text
- Reviewed
- Hits: 1406
- Visitors: 1596
- Downloads: 217
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 92 KB | Adobe Acrobat PDF | View Details Download |