Contribution in edited book
On the relationship between the McNaughton families of languages and the Chomsky hierarchy
Publication Details
Authors: | Beaudry, M.; Holzer, M.; Niemann, G.; Otto, F. |
Editor: | Kuich, W., Rozenberg, G. and Salomaa, A. |
Publisher: | Springer |
Place: | Berlin |
Publication year: | 2002 |
Pages range : | 340-348 |
Book title: | Developments in Language Theory, Proceedings DLT 2001 |
Title of series: | Lecture Notes in Computer Science 2295 |
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.
