Ordered Pure Multi-Pushdown Automata

• Autorzy: Meduna A. , Soukup O. , Zemek P.

Identyfikatory

DOI

10.20904/271025

• Języki publikacji: EN

Abstrakty

EN

In the presented paper we discuss pure versions of pushdown automata that have no extra non-input symbols. More specifically, we study pure multi-pushdown automata, which have several pushdown lists. We restrict these automata by the total orders defined over their pushdowns or alphabets and determine the accepting power of the automata restricted in this way. Moreover, we explain the significance of the achieved results and relate them to some other results in the automata theory.

Słowa kluczowe

EN

pure multi-pushdown automata; total orders; accepting power

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2015
• Tom: Vol. 27, No. 1
• Strony: 25--47
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Meduna A.

• Brno University of Technology, Faculty of Information Technology, IT4I Centre of Excellence, Božetĕchova 1/2, 612 66 Brno, Czech Republic

autor

Soukup O.

• Brno University of Technology, Faculty of Information Technology, IT4I Centre of Excellence, Božetĕchova 1/2, 612 66 Brno, Czech Republic

autor

Zemek P.

• Brno University of Technology, Faculty of Information Technology, IT4I Centre of Excellence, Božetĕchova 1/2, 612 66 Brno, Czech Republic

Bibliografia

• [1] A. Gabrielian. Pure grammars and pure languages. Int. J. Comput. Math., 9:3-16, 1981. DOI: 10.1080/00207168108803224.
• [2] E. Mäkinen. A note on pure grammars. Inf. Process. Lett., 23:271-274, 1986. DOI: 10.1016/0020-0190(86)90085-2.
• [3] H.A. Maurer, A. Salomaa, and D.Wood. Pure grammars. Information and Control, 44:47-72, 1980. DOI: 10.1016/S0019-9958(80)90131-X.
• [4] T. Masopust and A. Meduna. On pure multi-pushdown automata that perform complete pushdown pops. In Proceedings of the 12th International Conference on Automata and Formal Languages, pages 325-336, 2008.
• [5] T. Masopust and A. Meduna. On pure multi-pushdown automata that perform completepushdown pops. Acta Cybernetica, 19(2):537-552, 2009.
• [6] R. Bidlo, P. Blatnŷ, and A. Meduna. Automata with two-sided pushdowns defined over free groups generated by reduced alphabets. Kybernetika, 43(3):21-35, 2007.
• [7] M.A. Harrison and O.H. Ibarra. Multi-tape and multi-head pushdown automata. Information and Control, 13:433-470, 1968. DOI: 10.1016/S0019-9958(68)90901-7.
• [8] J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation, page 171. Addison-Wesley, 1979.
• [9] O.H. Ibarra. Generalizations of pushdown automata. PhD thesis, University of California, Berkeley, 1967.
• [10] D.C. Kozen. Automata and Computability, page 224. Springer, New York, 2007. DOI: 10.1007/978-1-4612-1844-9.
• [11] A. Meduna. Simultaneously one-turn two-pushdown automata. Int. J. Comput. Math., 2003(80):679-687, 2003. DOI: 10.1080/0020716031000070616.
• [12] D. Wood. Theory of Computation, page 274. Longman Higher Education, 1986.
• [13] L. Breveglieri, A. Cherubini, C. Citrini, and S.C. Reghizzi. Multi-push-down languages and grammars. Int. J. Found. Comput. Sci., 7(3):253-292, 1996. DOI: 10.1142/S0129054196000191.
• [14] M. Atig. From multi to single stack automata. In CONCUR 2010 - Concurrency Theory, volume 6269 of Lecture Notes in Computer Science, pages 117-131. 2010. DOI: 10.1007/978-3-642-15375-4 9.
• [15] M. Atig, B. Bollig, and P. Habermehl. Emptiness of multi-pushdown automata is 2etimecomplete. In Developments in Language Theory, volume 5257 of Lecture Notes in Computer Science, pages 121-133. 2008. DOI: 10.1007/978-3-540-85780-8 9.
• [16] N. Limaye and M. Mahajan. Membership testing: Removing extra stacks from multi-stack pushdown automata. In Language and Automata Theory and Applications, volume 5457 of Lecture Notes in Computer Science, pages 493-504. 2009. DOI: 10.1007/978-3-642-00982-2 42.
• [17] A. Seth. Global reachability in bounded phase multi-stack pushdown systems. In Computer Aided Verification, volume 6174 of Lecture Notes in Computer Science, pages 615-628. 2010. DOI: 10.1007/978-3-642-14295-6 53.
• [18] A. Meduna. Automata and Languages: Theory and Applications. Springer, London, 2000. DOI: 10.1007/978-1-4471-0501-5.
• [19] G. Rozenberg and A. Salomaa, editors. Handbook of Formal Languages, Vol. 1: Word, Language, Grammar. Springer, New York, 1997.
• [20] A. Salomaa. Formal Languages. Academic Press, London, 1973.
• [21] G. Pighizzini, J. Shallit, and M. Wang. Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. J. Comput. Syst. Sci., 65:393-414, 2002. DOI: 10.1006/jcss.2002.1855.