Church-Rosser groups and growing context-sensitive groups
| dc.date.accessioned | 2006-11-09T13:17:58Z | |
| dc.date.available | 2006-11-09T13:17:58Z | |
| dc.date.issued | 2006 | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2006110915636 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2006110915636 | |
| dc.format.extent | 247194 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | Church-Rosser language | eng |
| dc.subject | growing context-sensitive language | eng |
| dc.subject | word problem | eng |
| dc.subject | co-word problem | eng |
| dc.subject.ddc | 004 | |
| dc.title | Church-Rosser groups and growing context-sensitive groups | eng |
| dc.type | Preprint | |
| dcterms.abstract | A finitely generated group is called a Church-Rosser group (growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages. | eng |
| dcterms.accessRights | open access | |
| dcterms.creator | Kambites, Mark | |
| dcterms.creator | Otto, Friedrich | |
| dcterms.isPartOf | Mathematische Schriften Kassel ;; 06, 07 | ger |
| dcterms.source.journal | Mathematische Schriften Kassel | ger |
| dcterms.source.volume | 06, 07 |
