Shrinking Multi-pushdown Automata

1. Aanderaa, S.O.: On k-tape versus (k−1)-tape real time computation. In: Karp, R.M. (ed.) Complexity of Computation, SIAM-AMS Symp. in Appl. Math., vol. 7, pp. 75–96. American Math. Society, Providence (1974)

   Google Scholar 

2. Book, R.V.: Time-bounded grammars and their languages. J. Comput. System Sci. 5, 397–429 (1971)

   Article  MATH  MathSciNet  Google Scholar 

3. Book, R.V., Greibach, S.A.: Quasi-realtime languages. Math. Systems Theory 4, 97–111 (1970)

   Article  MATH  MathSciNet  Google Scholar 

4. Bordihn, H., Holzer, M., Kutrib, M.: Input reversals and iterated pushdown automata: A new characterization of khabbaz geometric hierarchy of languages. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 102–113. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

5. Buntrock, G.: Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakultät für Mathematik und Informatik, Universität Würzburg (1996)

   Google Scholar 

6. Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Inform. and Comput. 141, 1–36 (1998)

   Article  MATH  MathSciNet  Google Scholar 

7. Dahlhaus, E., Warmuth, M.: Membership for growing context-sensitive grammars is polynomial. J. Comput. System Sci. 33, 456–472 (1986)

   Article  MATH  MathSciNet  Google Scholar 

8. Holzer, M., Kutrib, M.: Flip-Pushdown Automata: k + 1 Pushdown Reversals Are Better Than k. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 490–501. Springer, Heidelberg (2003)

   Google Scholar 

9. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)

   MATH  Google Scholar 

10. McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach. 35, 324–344 (1988)

    MATH  MathSciNet  Google Scholar 

11. Niemann, G., Otto, F.: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. FOSSACS 1998 197, 1–21 (2005); An extended abstract appeared in Nivat, M. (ed.) FoSSaCS 1998. LNCS, vol. 1378, pp. 243–257. Springer, Berlin (1998)

    Article  MATH  MathSciNet  Google Scholar 

12. Otto, F., Moriya, E.: Shrinking alternating two-pushdown automata. IEICE Trans. on Inform. and Systems E87-D, 959–966 (2004)

    Google Scholar 

13. Paul, W.J.: On-line simulation of k + 1 tapes by k tapes requires nonlinear time. Inform. and Control 53, 1–8 (1982)

    Article  MATH  MathSciNet  Google Scholar 

14. Paul, W.J., Prauß, E., Reischuk, R.: On alternation. Acta Inform. 14, 243–255 (1980)

    Article  MATH  MathSciNet  Google Scholar 

15. Paul, W.J., Pippenger, N., Szemerédi, E., Trotter, W.T.: On determinism versus non-determinism and related problems. In: 24th Annual Symposium on Foundations of Computer Science, Proc., pp. 429–438. IEEE Computer Society, Los Angeles (1983)

    Google Scholar 

Download references