Journal article
McNaughton families of languages



Publication Details
Authors:
Beaudry, M.; Holzer, M.; Niemann, G.; Otto, F.
Publication year:
2003
Journal:
Theoretical Computer Science
Pages range:
1581-1628
Volume number:
290
ISSN:
0304-3975

Abstract
In 1988 the Church-Rosser languages were introduced by McNaughton et al. as those languages that are recognized by finite, length-reducing and confluent 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 fixed and the general membership problems for these families. (C) 2002 Elsevier Science B.V. All rights reserved.


Authors/Editors

Last updated on 2019-25-07 at 13:57