Preprint
Church-Rosser groups and growing context-sensitive groups
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.
Zitieren
@article{urn:nbn:de:hebis:34-2006110915636,
author={Kambites, Mark and Otto, Friedrich},
title={Church-Rosser groups and growing context-sensitive groups},
year={2006}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2006$n2006 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2006110915636 3000 Kambites, Mark 3010 Otto, Friedrich 4000 Church-Rosser groups and growing context-sensitive groups / Kambites, Mark 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2006110915636=x R 4204 \$dPreprint 4170 Mathematische Schriften Kassel ;; 06, 07 7136 ##0##urn:nbn:de:hebis:34-2006110915636
2006-11-09T13:17:58Z 2006-11-09T13:17:58Z 2006 urn:nbn:de:hebis:34-2006110915636 http://hdl.handle.net/123456789/2006110915636 247194 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Church-Rosser language growing context-sensitive language word problem co-word problem 004 Church-Rosser groups and growing context-sensitive groups Preprint 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. open access Kambites, Mark Otto, Friedrich Mathematische Schriften Kassel ;; 06, 07 Mathematische Schriften Kassel 06, 07
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden: