Projekt 5 - McNaughton Sprachen (McNaughton languages)

Fortsetzung von Projekt A13

(Beginn 10/2009)

The Church-Rosser languages were introduced by McNaughton et al. (1988) as the class languages that can be expressed as the set of ancestors of a certain final symbol with respect to a finite, length-reducing, and confluent string-rewriting system. In this definition apart from the final symbol, other non-terminal symbols are also allowed, e.g., for marking the left and the right border of the input strings.

By admitting other classes of finite string-rewriting systems in the definition this concept is generalized to yield the socalled McNaughton languages and its various subclasses. This concept is as powerful as the concept of the Turing machine or the concept of the phrase-structure grammar, and accordingly various complexity classes as well as most classes of the Chomsky hierachy can be characterized as certain classes of McNaughton languages.

In fact, two families of McNaughton languages are considered: those defined by finite (terminating) string-rewriting systems, and those defined by finite, terminating and confluent systems. The former can be shown to correspond to nondeterministic complexity and language classes, while the later correspond to deterministic complexity and language classes.

Of particular interest are the low classes of the McNaughton hierarchy as they seem to not coincide with any known complexity or language class. We are concerned with the relationships between the various classes of McNaughton languages, their closure and non-closure properties, and the complexity of their membership problems.

Mitarbeiter:

Dr. Peter Leupold

Peter Černo

Dr. František Mráz

Veröffentlichungen:

Otto, F., Černo P. and Mráz F.:
On the classes of languages accepted by limited context restarting automata
RAIRO Informatique Théorique et Applications 48 (2014) 61-84
Mráz, F. and Otto, F.:
Lambda-confluence is undecidable for clearing restarting automata. In Konstantinidis, S.,editors, CIAA 2013 Proc., Lecture Notes in Computer Science 7982, Springer, Berlin, (2013), pages 256--267.
Otto, F., Černo P. and Mráz F.:
Limited context restarting automata and McNaughton families of languages.
In Freund, R., Holzer, M., Truthe, B. and Ultes-Nitsche, U., editors, Fourth Workshop on Non-Classical Models for Automata and Applications (NCMA 2012), Proc., books@ocg.at, Band 290, pages 156-180, Österreichische Computer Gesellschaft, Wien, 2012.
Leupold, P. and Otto, F.:
On McNaughton families of languages specified by certain variants of monadic string-rewriting systems.
Fundamenta Informaticae 112 (2011) 219-238
Leupold, P. and Otto, F.:
On McNaughton families of languages specified by certain variants of monadic string-rewriting systems.
In Bordihn, H., Freund, R., Hinze, T., Holzer, M., Kutrib, M. and Otto, F., editors, Second Workshop on Non-Classical Models for Automata and Applications (NCMA 2010), Proc., books@ocg.at, Band 263, pages 112-126, Österreichische Computer Gesellschaft, Wien, 2010.