Categories and Subject Descriptors: F.1.1 [Computation by Abstract Devices]: Models of Computation -- automata; F.4.3 [Mathematical Logic and Formal Languages]: Formal Languages -- decision problems
General Terms: Algorithms, Languages, Theory
Additional Key Words and Phrases: dpda equivalence, finite-turn dpdas, real time dpdas, deterministic languages
Selected references
- S. A. Greibach. Linearity is polynomially decidable for realtime pushdown store automatia. Information and Control, 42(1):27-37, July 1979.
- 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.
- Michio Oyamaguchi and Namio Honda. The decidability of equivalence for determistic stateless pushdown automata. Information and Control, 38(3):367-376, September 1978.
- D. J. Rosenkrantz and R. E. Stearns. Properties of deterministic top-down grammars. Information and Control, 17(3):226-256, October 1970.
- Leslie G. Valiant. The equivalence problem for deterministic finite-turn pushdown automata. Information and Control, 25(2):123-133, June 1974.