Ordered Pure Multi-Pushdown Automata

Alexander Meduna, Ondřej Soukup, Peter Zemek


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.

Full Text:



A. Gabrielian. Pure grammars and pure languages. Int. J. Comput. Math., 9:3–16, 1981. DOI: 10.1080/00207168108803224

E. Makinen. A note on pure grammars. Information Processing Letters, 23:271–274, 1986. DOI: 10.1016/0020-0190(86)90085-2

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

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.

T. Masopust and A. Meduna. On pure multi-pushdown automata that perform complete-pushdown pops. Acta Cybernetica, 19(2):537–552, 2009.

R. Bidlo, P. Blatny, and A. Meduna. Automata with two-sided pushdowns defined over free groups generated by reduced alphabets. Kybernetika, 43(3):21–35, 2007.

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

J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation, page 171. Addison-Wesley, 1979.

O.H. Ibarra. Generalizations of pushdown automata. PhD thesis, University of California, Berkeley, 1967.

D.C. Kozen. Automata and Computability, page 224. Springer, New York, 2007. DOI: 10.1007/978-1-4612-1844-9

A. Meduna. Simultaneously one-turn two-pushdown automata. Int. J. Comput. Math., 2003(80):679–687, 2003. DOI: 10.1080/0020716031000070616

D. Wood. Theory of Computation, page 274. Longman Higher Education, 1986.

L. Breveglieri, A. Cherubini, C. Citrini, and S.C. Reghizzi. Multi-push-down lan- guages and grammars. Int. J. Found. Comput. Sci., 7(3):253–292, 1996. DOI: 10.1142/S0129054196000191

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

M. Atig, B. Bollig, and P. Habermehl. Emptiness of multi-pushdown automata is 2etime-complete. 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

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

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

A. Meduna. Automata and Languages: Theory and Applications. Springer, London, 2000. DOI: 10.1007/978-1-4471-0501-5

G. Rozenberg and A. Salomaa, editors. Handbook of Formal Languages, Vol. 1: Word, Language, Grammar. Springer, New York, 1997.

A. Salomaa. Formal Languages. Academic Press, London, 1973.

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

DOI: http://dx.doi.org/10.20904/271025


  • There are currently no refbacks.

Copyright (c) 2015 Alexander Meduna, Ondřej Soukup, Peter Zemek

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN: 1896-5334 (print), 2300-889X (online)

Open Acces CrossRef Indexed in DOAJ