Church-Rosser Languages and Related Classes

Niemann, Gundula

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

URN: urn:nbn:de:0002-0028

Zugl.: Kassel, Univ., Diss. 2002

| Preis und lieferbare Formen -->

Inhalt: 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.

Die Publikation ist in folgenden Formen erhältlich:

Volltext (pdf-Datei, nicht ausdruckbar - 2.49 MB)
PDF ansehen (view)
Volltext (pdf-Datei, ausdruckbar, kostenpflichtig - 2.49 MB) 10.00 Euro
(kostenfrei im Netz der Universität Kassel - Im Netz der Uni Kassel befinden Sie sich, wenn Sie z.B. an einem Rechner im ITS, Ihrem Arbeitsplatz an der Uni oder auch in der Multimediathek der Bibliothek befinden.)
PDF erwerben (download) - Achtung kostenpflichtig, da Sie sich zur Zeit nicht im Netz der Uni-Kassel befinden