Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
217--228
Opis fizyczny
Bibliogr. 14 poz.
Twórcy
autor
- Fachbereich Mathematik/Informatik Universit¨at Kassel, Germany
autor
- Fachbereich Mathematik/Informatik Universit¨at Kassel, Germany
autor
- Charles University,Faculty of Mathematics and Physics, Department of Computer Science, Malostramske nam. 25. CZ-11800 Praha 1, Czech Republic
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0005-0124