Beitrag in einem Sammelband
On the relationship between the McNaughton families of languages and the Chomsky hierarchy
Details zur Publikation
Autor(inn)en: | Beaudry, M.; Holzer, M.; Niemann, G.; Otto, F. |
Herausgeber: | Kuich, W., Rozenberg, G. and Salomaa, A. |
Verlag: | Springer |
Verlagsort / Veröffentlichungsort: | Berlin |
Publikationsjahr: | 2002 |
Seitenbereich: | 340-348 |
Buchtitel: | Developments in Language Theory, Proceedings DLT 2001 |
Titel der Buchreihe: | Lecture Notes in Computer Science 2295 |
Zusammenfassung, Abstract
By generalizing the Church-Rosser languages the McNaughton families of languages are obtained. Here we concentrate on those families that are defined by monadic or special string-rewriting systems. We investigate the relationship of these families to each other and to the lower classes of the Chomsky hierarchy and present some closure and some non-closure properties for them. Moreover, we address some complexity issues for their membership problems.
By generalizing the Church-Rosser languages the McNaughton families of languages are obtained. Here we concentrate on those families that are defined by monadic or special string-rewriting systems. We investigate the relationship of these families to each other and to the lower classes of the Chomsky hierarchy and present some closure and some non-closure properties for them. Moreover, we address some complexity issues for their membership problems.
