Journal of the ACM Bibliography
Esko Ukkonen. The equivalence
problem for some non-real-time deterministic pushdown automata.
Journal of the ACM, 29(4):1166-1181, October 1982.
[BibTeX entry]
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.
Shortcuts: