Deterministic Two-Way Restarting Automata and Marcus Contextual Grammars

• Autorzy: Jurdziński T. , Otto F. , Mráz F. , Plátek M.
• Języki publikacji: EN

Abstrakty

EN

It is known that for (right-) monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right-left-monotone. Moreover, we present a transformation of this kind of restarting automata into contextual grammars with regular selection.

Słowa kluczowe

EN

contextual grammars; restarting automata; right-left monotonicity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 217--228
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Jurdziński T.

• Fachbereich Mathematik/Informatik Universit¨at Kassel, Germany

autor

Otto F.

• Fachbereich Mathematik/Informatik Universit¨at Kassel, Germany

autor

Mráz F.

• Charles University,Faculty of Mathematics and Physics, Department of Computer Science, Malostramske nam. 25. CZ-11800 Praha 1, Czech Republic

autor

Plátek M.

• Charles University,Faculty of Mathematics and Physics, Department of Computer Science, Malostramske nam. 25. CZ-11800 Praha 1, Czech Republic

Bibliografia

• [1] Aho, A.V., Hopcroft, J.E., Ullman, U.: A General Theory of Translation, Mathematical Systems Theory, 3(3), 1969, 193–221.
• [2] Hopcroft, J.E., Ullman, J.D.: An Approach to a Unified Theory of Automata, The Bell System Technical Journal, 46, 1967, 1793–1829.
• [3] Jančar, P., Mráz, F., Plátek, M., Procházka, M., Vogel, J.: Restarting Automata and Marcus Grammars, Forschungsergebnisse der Fakultät für Mathematik und Informatik Math/95/1, Institut für Informatik, Friedrich-Schiller-Universität Jena, 1995.
• [4] Jančar, P., Mráz, F., Plátek, M., Procházka, M., Vogel, J.: Restarting Automata, Marcus Grammars and Context-Free Languages, in: Developments in Language Theory II (J. Dassow, G. Rozenberg, A. Salomaa, Eds.),World Scientific, Singapore, 1996, 102–111.
• [5] Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting Automata, in: FCT’95 (H. Reichel, Ed.), LNCS 965, Springer, Berlin, 1995, 283–292.
• [6] Jurdziński, T., Mráz, F., Otto, F., Plátek, M.: Deterministic Two-Way Restarting Automata Don’t Need Auxiliary Symbols If They Are (Right-, Left-, Right-Left-) Monotone, Math. Schriften Univ. Kassel 7/2004.
• [7] Marcus, S.: Contextual Grammars, Revue Roum. Math. Pures Appl., 14(10), 1969, 1525–1534.
• [8] Marcus, S.: Contextual Grammars and Natural Languages, in: Handbook of Formal Languages. Vol. 2: Linear Modeling: Background and Application (G. Rozenberg, A. Salomaa, Eds.), Springer, Berlin, 1997, 215–235.
• [9] Mráz, F., Plátek, M., Procházka, M.: Restarting Automata, Deleting, and Marcus Grammars, in: Recent Topics in Mathematical and Computational Linguistics (C. Mart´ın-Vide, G. P˘aun, Eds.), The Publishing House of the Romanian Academy, Bucharest, 2000, 218–233.
• [10] Otto, F.: Restarting Automata - Notes for a Course at the 3rd International PhD School in Formal Languages and Applications, Math. Schriften Univ. Kassel 6/2004.
• [11] Otto, F., Jurdzi´nski, T.: On Left-Monotone Restarting Automata, Math. Schriften Univ. Kassel, 17/2003.
• [12] Păun, G.: Marcus Contextual Grammars, Kluwer, Dordrecht, 1998.
• [13] Plátek, M.: Two-Way Restarting Automata and j-Monotonicity, in: SOFSEM 2001: Theory and Practice of Informatics, 28th Conference on Current Trends in Theory and Practice of Informatics (L. Pacholski, P. Ružička, Eds.), LNCS 2234, Springer, Berlin, 2001, 316–325.
• [14] Plátek, M., Otto, F., Mráz, F.: Restarting Automata and Variants of j-Monotonicity, in: Descriptional Complexity of Formal Systems, Proceedings of DCFS 2003 (E. Csuhaj-Varj´u, C. Kintala, D. Wotschke, G. Vaszil, Eds.), MTA SZTAKI, Budapest, 2003, 303–312.