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.
Martin Beaudry
(Université de Sherbrooke, Sherbrooke, Québec, Canada)
Markus Holzer
(Fachbereich Informatik, Technische Universität München)