Flip-Pushdown Automata: Nondeterminism is Better than Determinism

  • Markus Holzer
  • Martin Kutrib
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


Flip-pushdown automata are pushdown automata with the additional ability to flip or reverse its pushdown. We investigate deterministic and nondeterministic flip-pushdown automata accepting by final state or empty pushdown. In particular, for nondeterministic flip-pushdown automata both acceptance criterion are equally powerful, while for determinism, acceptance by empty pushdown is strictly weaker. This nicely fits into the well-known results on ordinary pushdown automata. Moreover, we consider hierarchies of flip-pushdown automata w.r.t. the number of pushdown reversals. There we show that nondeterminism is better than determinism. Moreover, since there are languages which can be recognized by a deterministic flip-pushdown automaton with k + 1 pushdown reversals but which cannot be recognized by a k-flip-pushdown (deterministic or nondeterministic) as shown in [9] we are able to complete our investigations with incomparability results on different levels of the hierarchies under consideration.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Ch. Bader and A. Moura. A generalization of Ogden’s lemma. Journal of the ACM, 29(2):404–407, 1982.zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    N. Chomsky. Handbook of Mathematic Psychology, volume 2, chapter Formal Properties of Grammars, pages 323–418. Wiley & Sons, New York, 1962.Google Scholar
  3. 3.
    S. N. Coole. Deterministic pushdown store machines and real-time computations. Journal of the ACM, 18:306–328, 1971.CrossRefGoogle Scholar
  4. 4.
    R. J. Evey. The Theory and Applications of Pushdown Store Machines. Ph.D thesis, Harvard University, Massachusetts, May 1963.Google Scholar
  5. 5.
    S. Ginsburg. Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland, Amsterdam, 1975.zbMATHGoogle Scholar
  6. 6.
    S. Ginsburg, S. A. Greibach, and M. A. Harrison. One-way stack automata. Journal of the ACM, 14(2):389–418, April 1967.zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    S. Ginsburg and E. H. Spanier. Finite-turn pushdown automata. SIAM Journal on Computing, 4(3):429–453, 1966.zbMATHMathSciNetGoogle Scholar
  8. 8.
    S. A. Greibach. An infinite hierarchy of context-free languages. Journal of the ACM, 16(1):91–106, January 1969.zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    M. Holzer and M. Kutrib. Flip-pushdown automata: k +1 pushdown reversals are better than k. In Proceedings of the 30th International Colloquium on Automata, Languages, and Programming, LNCS, Eindhoven, Netherlands, June–July 2003. Springer. To appear.Google Scholar
  10. 10.
    G. Rozenberg and A. Salomaa. The Mathematical Theory of L Systems, volume 90 of Pure and Applied Mathematics. Academic Press, 1980.Google Scholar
  11. 11.
    P. Sarkar. Pushdown automaton with the ability to flip its stack. Report TR01-081, Electronic Colloquium on Computational Complexity (ECCC), November 2001.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Markus Holzer
    • 1
  • Martin Kutrib
    • 2
  1. 1.Institut für InformatikTechnische Universität MünchenGarching bei MünchenGermany
  2. 2.Institut für InformatikUniversität GiessenGiessenGermany

Personalised recommendations