McNaughton families of languages

✍ Scribed by M. Beaudry; M. Holzer; G. Niemann; F. Otto

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 410 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00070-1

✦ Synopsis

In 1988 the Church-Rosser languages were introduced by McNaughton et al. as those languages that are recognized by ÿnite, length-reducing and con uent string-rewriting systems using extra non-terminal symbols. Here we generalize this concept by considering classes of languages that are obtained by other types of string-rewriting systems. To honour Robert McNaughton's original contribution we call the resulting families of languages McNaughton families.

Here it is shown that the concept of McNaughton families is as powerful as the notion of Turing machine or the notion of phrase-structure grammar. We investigate the relationships between the various McNaughton families, obtaining an extensive hierarchy of classes that includes many well-known language and complexity classes as well as some new classes. Further, we consider some closure and non-closure properties for those McNaughton families that are contained in the class of context-free languages, and we address the complexity of the ÿxed and the general membership problems for these families.