References

  1. Alfred V. Aho, John E. Hopcroft & Jeffrey D. Ullman (1968): Time and tape complexity of pushdown automaton languages. Information and Control 13(3), pp. 186–206, doi:10.1016/S0019-9958(68)91087-5.
  2. Torben Amtoft & Jesper Larsson Träff (1992): Partial memoization for obtaining linear time behavior of a 2DPDA. Theoretical Computer Science 98(2), pp. 347–356, doi:10.1016/0304-3975(92)90008-4.
  3. Nils Andersen & Neil D. Jones (1994): Generalizing Cook's transformation to imperative stack programs. In: J. Karhumäki, H. Maurer & G. Rozenberg: Results and Trends in Theoretical Computer Science, LNCS 812. Springer-Verlag, pp. 1–18, doi:10.1007/3-540-58131-6_33.
  4. Stephen A. Cook (1972): Linear time simulation of deterministic two-way pushdown automata. In: C. V. Freiman, J. E. Griffith & J. L. Rosenfeld: Information Processing 71. North-Holland, pp. 75–80.
  5. John E. Hopcroft & Jeffrey D. Ullman (1979): Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.
  6. Neil D. Jones (1977): A note on linear time simulation of deterministic two-way pushdown automata. Information Processing Letters 6(4), pp. 110–112, doi:10.1016/0020-0190(77)90022-9.
  7. Neil D. Jones (1997): Computability and Complexity: From a Programming Language Perspective. Foundations of Computing. MIT Press, Cambridge, Massachusetts.
  8. Donald E. Knuth, James H. Morris & Vaughan R. Pratt (1977): Fast pattern matching in strings. SIAM Journal on Computing 6(2), pp. 323–350, doi:10.1137/0206024.
  9. Donald Michie (1968): ``Memo'' functions and machine learning. Nature 218(5136), pp. 19–22, doi:10.1038/218019a0.
  10. Torben Æ. Mogensen (1994): WORM-2DPDAs: an extension to 2DPDAs that can be simulated in linear time. Information Processing Letters 52(1), pp. 15–22, doi:10.1016/0020-0190(94)90134-1.

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org