Additional Key Words and Phrases: pushdown automaton, deterministic, decision procedure, complexity, regularity, program schema
Selected references
- Seymour Ginsburg and Sheila A. Greibach. Deterministic context free languages. Information and Control, 9(6):620-648, December 1966.
- A. J. Korenjak and J. E. Hopcroft. Simple deterministic languages. In Conference Record of 1966 Seventh Annual Symposium on Switching and Automata Theory, pages 36-46, Berkeley, California, 26-28 October 1966. IEEE.
- P. M. Lewis II and R. E. Stearns. Syntax-directed transduction. Journal of the ACM, 15(3):465-488, July 1968.
- A. R. Meyer and M. J. Fischer. Economy of description by automata, grammars, and formal systems. In Conference Record 1971 Twelfth Annual Symposium on Switching and Automata Theory, pages 188-191, East Lansing, Michigan, 13-15 October 1971. IEEE.
- D. J. Rosenkrantz and R. E. Stearns. Properties of deterministic top-down grammars. Information and Control, 17(3):226-256, October 1970.
- R. E. Stearns. A regularity test for pushdown machines. Information and Control, 11(3):323-340, September 1967.
- Leslie G. Valiant. The equivalence problem for deterministic finite-turn pushdown automata. Information and Control, 25(2):123-133, June 1974.