The equivalence problem for real-time DPDAs
- 1 July 1987
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 34 (3) , 731-760
- https://doi.org/10.1145/28869.28881
Abstract
The equivalence problem for deterministic real-time pushdown automata is shown to be decidable. This result is obtained by showing that Valiant's parallel stacking technique using a replacement function introduced in this paper succeeds for deterministic real-time pushdown automata. Equivalence is also decidable for two deterministic pushdown automata, one of which is real-time.Keywords
This publication has 21 references indexed in Scilit:
- An extended direct branching algorithm for checking equivalence of deterministic pushdown automataTheoretical Computer Science, 1984
- An axiomatic approach to the Korenjak-Hopcroft algorithmsTheory of Computing Systems, 1983
- The equivalence problem for some non-real-time deterministic pushdown automataJournal of the ACM, 1982
- The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machineJournal of Computer and System Sciences, 1981
- The simultaneous accessibility of two configurations of two equivalent DPDA'sInformation Processing Letters, 1981
- On equivalence of grammars through transformation treesTheoretical Computer Science, 1979
- Two decidability results for deterministic pushdown automataJournal of Computer and System Sciences, 1979
- A representation of trees by languages IITheoretical Computer Science, 1978
- Equivalence problems for deterministic context-free languages and monadic recursion schemesJournal of Computer and System Sciences, 1977
- An improvement on valiant's decision procedure for equivalence of deterministic finite turn pushdown machinesTheoretical Computer Science, 1976