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.


Autor(inn)en / Herausgeber(innen)

Zuletzt aktualisiert 2019-25-07 um 11:59