Church-Rosser Languages and Related Classes

Niemann, Gundula

kassel university press, ISBN: 978-3-89958-002-0, 2003, 123 Pages

URN: urn:nbn:de:0002-0028

Zugl.: Kassel, Univ., Diss. 2002

| Price and available forms -->

Content: In the present thesis we show that the class of Church-Rosser languages CRL has several characterizations through different concepts from
string-rewriting and automata theory. This answers questions concerning the exact position of CRL in relation to other language classes that have been open for a long time. We also investigate the closure properties of CRL and present some typical examples of languages that are or are not included in this class.

The ''nondeterministic counterpart'' of CRL is the class GCSL of growing context-sensitive languages. Our main result concerning this class is its characterization by acyclic context-sensitive grammars. This result is counterintuitive and sheds some light on the limits of "information transport'' within a string during its production by weight-increasing rules.

Then we have a closer look at the inner structure and power of CRL by investigating two of its strict subclasses. Finally we turn our attention to some language classes that are defined by restarting automata. Also in this concept we obtain characterizations for the classes CRL and GCSL. Then we show that the most general types of restarting automata recognize some languages that are not growing context-sensitive and even some NP-complete languages. This indicates that the question of separating the most general language class defined by restarting automata from the class CSL of context-sensitive languages is quite hard.

In der vorliegenden Arbeit wird gezeigt, dass die Klasse der Church-Rosser-Sprachen CRL verschiedene Charakterisierungen in unterschiedlichen Konzepten sowohl aus dem Gebiet der Wortersetzungssysteme als auch aus dem Gebiet der Automatentheorie besitzt. Dies beantwortet lange offen gebliebene Fragen zur genauen Lage von CRL im Verhältnis zu anderen Sprachklassen. Wir untersuchen außerdem die Abschlusseigenschaften von CRL und betrachten einige typische Beispiele von Sprachen, die in CRL enthalten oder nicht enthalten sind.

Das "nichtdeterministische Gegenstück" von CRL ist die Klasse GCSL der wachsend kontextsensitiven Sprachen. Unser Hauptresultat in Bezug auf die
Klasse GCSL ist ihre Charakterisierung durch azyklische kontextsensitive Grammatiken. Dieses Resultat ist kontraintuitiv und beleuchtet die Grenzen des "Informationstransportes" innerhalb eines Wortes während der Erzeugung mit gewichtserhöhenden Regeln.

Dann betrachten wir die innere Struktur und Mächtigkeit von CRL, indem wir zwei ihrer echten Teilklassen näher untersuchen. Anschließend wenden wir uns
einigen Sprachklassen zu, die durch Restart-Automaten definiert werden. Auch in diesem Konzept erhalten wir Charakterisierungen der Klassen CRL und GCSL.
Daneben zeigen wir, dass die allgemeinsten Typen von Restart-Automaten einige Sprachen erkennen, die nicht wachsend kontextsensitiv sind, und sogar einige
NP-vollständige Sprachen. Die allgemeinste von Restart-Automaten definierte Sprachklasse von der Klasse CSL der kontextsensitiven Sprachen zu trennen, stellt sich damit als eine sehr schwierige Aufgabe heraus.

Publication is available in following forms:

Full text (pdf-file, not printable - 2.49 MB)
view PDF
Full text (pdf-file, printable, with costs - 2.49 MB) 10.00 Euro
(free of charge in kassel University network - you are in kassel University network if you are in the workplace, or you are using a pc in the ITS or in the library)
download PDF - Attention! with costs, because you are not in kassel University network!