KOBRA - Dokumentenserver der Universität Kassel  → Fachbereiche  → FB 10 / Mathematik und Naturwissenschaften  → Institut für Mathematik  → Mathematische Schriften Kassel 

Please use this identifier to cite or link to this item: http://nbn-resolving.de/urn:nbn:de:hebis:34-2006110915636

Title: Church-Rosser groups and growing context-sensitive groups
Authors: Kambites, MarkOtto, Friedrich
???metadata.dc.subject.ddc???: 004 - Informatik (Data processing Computer science)
Issue Date: 2006
Series/Report no.: Mathematische Schriften Kassel06, 07
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.
URI: urn:nbn:de:hebis:34-2006110915636
Appears in Collections:Mathematische Schriften Kassel

Files in This Item:

File Description SizeFormat
prep0607.pdf247.14 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License
Creative Commons

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.