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.


Authors/Editors

Last updated on 2019-25-07 at 11:59