Affiliations: Universitat Rovira i Virgili, Av. Catalunya, 35, 43002 Tarragona, Spain. Peter.Leupold@web.de | Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany. otto@theory.informatik.uni-kassel.de
Note: [] The work presented here was performed while Peter Leupold was a Return Fellow of the Alexander-von-Humboldt Foundation visiting at Fachbereich Elektrotechnik/Informatik, Universität Kassel.
Note: [] Address for correspondence: Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany
Abstract: We study the McNaughton families of languages that are specified by four different variants of monadic string-rewriting systems: strictly monadic systems, monadic systems, inverse context-free systems, and generalized monadic systems. In the general case these four variants yield the same McNaughton family of languages, which coincides with the class of context-free languages. In the case of confluent systems, however, we obtain two McNaughton families by showing that special rules, that is, rules with empty right-hand side, are not needed. This implies that in this situation strictly monadic systems are as expressive as monadic systems, and inverse context-free systems are as expressive as generalized monadic systems. The McNaughton family defined by the former systems is contained in the McNaughton family that is defined by the latter systems, and this inclusion is proper if and only if the former family is not closed under inverse alphabetic morphisms. Finally, we show that the latter family is a proper subclass of the class of deterministic context-free languages.
