Show simple item record

dc.date.accessioned2006-11-09T13:17:58Z
dc.date.available2006-11-09T13:17:58Z
dc.date.issued2006
dc.identifier.uriurn:nbn:de:hebis:34-2006110915636
dc.identifier.urihttp://hdl.handle.net/123456789/2006110915636
dc.format.extent247194 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.subjectChurch-Rosser languageeng
dc.subjectgrowing context-sensitive languageeng
dc.subjectword problemeng
dc.subjectco-word problemeng
dc.subject.ddc004
dc.titleChurch-Rosser groups and growing context-sensitive groupseng
dc.typePreprint
dcterms.abstractA 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.accessRightsopen access
dcterms.creatorKambites, Mark
dcterms.creatorOtto, Friedrich
dcterms.isPartOfMathematische Schriften Kasselger
dcterms.isPartOf06, 07ger


Files in this item

Thumbnail
Thumbnail
Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record