DSpace
KOBRA
KOBRA

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

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://nbn-resolving.de/urn:nbn:de:hebis:34-2006110915636

Titel: Church-Rosser groups and growing context-sensitive groups
Autor(en): Kambites, MarkOtto, Friedrich
Klassifikation (DDC): 004 - Informatik (Data processing Computer science)
Erscheinungsdatum: 2006
Serie/Report Nr.: Mathematische Schriften Kassel06, 07
Zusammenfassung: 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
Sammlung(en):Mathematische Schriften Kassel

Dateien zu dieser Ressource:

Datei Beschreibung GrößeFormat
prep0607.pdf247,14 kBAdobe PDFÖffnen/Anzeigen

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons
Creative Commons

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.