On McNaughton Families of Languages That Are Specified by Some Variants of Monadic String-Rewriting Systems

• Autorzy: Leupold P. , Otto F.
• Języki publikacji: EN

Abstrakty

EN

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 alphabeticmorphisms. Finally, we show that the latter family is a proper subclass of the class of deterministic context-free languages.

Słowa kluczowe

EN

McNaughton languages; strictly monadic systems; monadic systems; inverse context free systems; generalized monadic systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 2/3
• Strony: 219--238
• Opis fizyczny: Bibliogr. 16 poz., wykr.

Twórcy

autor

Leupold P.

autor

Otto F.

• Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany,

Bibliografia

• [1] J. Autebert, J. Berstel, and L. Boasson. Context-free languages and pushdown automata. In: G. Rozenberg and A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, pages 111-174. Springer, Berlin-Heidelberg, 1997.
• [2] M. Beaudry,M. Holzer, G. Niemann, and F. Otto. McNaughton families of languages. Theoretical Computer Science 290 (2003) 1581-1628.
• [3] R.V. Book and F. Otto. String-Rewriting Systems. Springer, New York, 1993.
• [4] G. Buntrock and F. Otto. Growing context-sensitive languages and Church-Rosser languages. Information and Computation 141 (1998) 1-36.
• [5] M. Cavaliere and P. Leupold. Observation of string-rewriting systems. Fundamenta Informaticae 74 (2006) 447-462.
• [6] E. Dahlhaus and M. Warmuth. Membership for growing context-sensitive grammars is polynomial. Journal of Computer and System Sciences 33 (1986) 456-472.
• [7] M. Harrison. Introduction to Formal Language Theory. Addison-Wesley, Reading, Massachusetts, 1978.
• [8] D. Hofbauer and J. Waldmann. Deleting string rewriting systems preserve regularity. Theoretical Computer Science 327 (2004) 301-317.
• [9] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts, 1979.
• [10] D. Knuth and P. Bendix. Simple word problems in universal algebras. In: J. Leech (ed.), Computational Problems in Abstract Algebra, pages 263-297. Pergamon Press, New York, 1970.
• [11] T. Kretschmer. A closure property of regular languages. Theoretical Computer Science 61 (1988) 283-287.
• [12] R. McNaughton, P. Narendran, and F. Otto. Church-Rosser Thue systems and formal languages. Journal of the Association for Computing Machinery 35 (1988) 324-344.
• [13] K. Madlener, P. Narendran, F. Otto, and L. Zhang. On weakly confluent monadic string-rewriting systems. Theoretical Computer Science 113 (1993) 119-165.
• [14] M.H.A. Newman. On theories with a combinatorial definition of "equivalence." Annals Math. 43 (1943) 223-243.
• [15] G. Niemann and F. Otto. The Church-Rosser languages are the deterministic variants of the growing contextsensitive languages. Information and Computation 197 (2005) 1-21.
• [16] F. Otto. Restarting automata. In Z. ´Esik, C. Martin-Vide, and V. Mitrana (eds.), Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence, Vol. 25, 269-303. Springer, Berlin, 2006.