article

Free access

The equivalence problem for real-time DPDAs

Author:

Michio OyamaguchiAuthors Info & Claims

Journal of the ACM (JACM), Volume 34, Issue 3

Pages 731 - 760

https://doi.org/10.1145/28869.28881

Published: 01 July 1987 Publication History

PDF eReader

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.

References

[1]

BEERI, C. An improvement on Valiant's decision procedure for equivalence of deterministic pushdown machines. Theoret. Comput. Sci. 3 (1976), 305-320.

Google Scholar

[2]

COURCELLE, B. A representation of trees by languages. I. Theoret. Comput. Sci. 6 (1978), 225-279.

Google Scholar

[3]

COURCELLE, i. A representation of trees by languages. If. Theoret. Comput. Sci. 7 (1978), 25-55.

Google Scholar

[4]

COURCELLE, B. The simultaneous accessibility of two configurations of two equivalent DPDAs. Inf. Proc. Lett. 12 (1981), 111-114.

Google Scholar

[5]

COURCELLE, B. An axiomatic approach to the Korenjak-Hopcroft algorithms. Math. Syst. Theory 16 (1983), 191-231.

Google Scholar

[6]

FRIEDMAN, E. P. Equivalence problems for deterministic context-free languages and monadic recursion schemes. J. Comput. Syst. Sci. 14 (1977), 344-359.

Google Scholar

[7]

FRIEDMAN, E. e., AND GREIBACH, S.A. Superdeterministic DPDAs: The method of accepting does affect decision problems. 3. Comput. Syst. Sci. 19 (1979), 79-117.

Google Scholar

[8]

FRIEDMAN, E. P., AND GREIBACH, S.A. A polynomial time algorithm for deciding the equivalence problem for 2-tape deterministic finite state acceptors. SIAM J. Comput. 11 (1982), 166-183.

Google Scholar

[9]

HARRISON, M. A., AND HAVEL, I.i. Real-time strict deterministic languages. SIAM J. Comput. 1 (1972), 333-349.

Google Scholar

[10]

HARRISON, M. A., HAVEL, I. M., AND YEHUDAI, A. On equivalence of grammars through transformation trees. Theoret. Comput Sci. 9 (1979), 173-205.

Google Scholar

[11]

ITZHAIK, Y., AND YEHUDAI, A. A decision procedure for the equivalence of two DPDAs, one of which is linear. In Lecture Notes in Computer Science, vol. I 15. Springer-Verlag, New York, 198 l, 229-237.

Crossref

Google Scholar

[12]

KATAYAMA, T., TSUCmVA, N., AND ENOMOTO, H. On the decidability of equivalence for deterministic pushdown transducers. Trans. IECE Japan 58-D (1975), 760-767.

Google Scholar

[13]

KORENJAK, A. J., AND HOPCROFT, J. E. Simple deterministic languages. In Proceedings of the IEEE 7th Symposium on Switching and Automata Theory. IEEE, New York, 1966, pp. 36-46.

Google Scholar

[14]

LINNA, M. Two decidability results for deterministic pushdown automata. 3. Comput. Syst. Sci. 18 (1979), 92-107.

Google Scholar

[15]

OYAMAGUCHI, M., AND HONDA, N. The decidability of equivalence for deterministic stateless pushdown automata. Inf. Control 38 (1978), 367-376.

Google Scholar

[16]

OYAMAGUCHI, M., INAGAKI, Y., AND HONDA, N. The equivalence problem for real-time strict deterministic languages. Inf. Control 45 (1980), 90-115.

Google Scholar

[17]

OYAMAGUCHI, M., INAGAKI, Y., AND HONDA, N. On the equivalence problem for two dpda's, one of which is real-time. Inf. Proc. 80 (1980), 53-57.

Google Scholar

[18]

OYAMAGUCHI, M., INAGAKI, Y., AND HONDA, N. The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine. J. Comput. Syst. Sci. 23 (1981), 366-382.

Google Scholar

[19]

ROSENKRANTZ, n. Z., AND STEARNS, R.E. Properties of deterministic topdown grammars. Inf. Control 17 (1970), 226-256.

Google Scholar

[20]

SEKIMOTO, S. An extended result on the equivalence problem for LR machines taking monotonous -moves. Trans. IECE Japan 64-D ( 1981), 419-426.

Google Scholar

[21]

SEKIMOTO, S. On the equivalence problem for deterministic finite-turn pushdown automata. Trans. IECE Japan 64-D (1981), 463-470.

Google Scholar

[22]

TANIGUCHI, K., AND KASAMI, T. A result on the equivalence problem for deterministic pushdown automata. J. Comput. Syst. Sci. 13 (1976), 38-50.

Google Scholar

[23]

TOMITA, E. A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata. Inf. Control 52 (1982), 187-238.

Google Scholar

[24]

TOMITA, E. An extended direct branching algorithm for checking equivalence of deterministic pushdown automata. Theoret. Comput. Sci. 32 (1984), 87-120.

Crossref

Google Scholar

[25]

UKKONEN, E. The equivalence problem for some non-real-time deterministic pushdown automata. J. ACM 29, 4 (Oct. 1982), 1 t66-1181.

Crossref

Google Scholar

[26]

VALIANT, L.G. Decision procedures for families of deterministic pushdown automata. Ph.D. dissertation, Univ. of Warwick, Warwick, England, July 1973.

Google Scholar

[27]

VALIANT, L.G. The equivalence problem for deterministic finite-turn pushdown automata. Inf. Control 25 (1974), 123-133.

Google Scholar

[28]

VALIANT, L. G., AND PATERSON, M.S. Deterministic one counter automata. J. Comput. Syst. Sci. lO (1975), 340-350.

Google Scholar

[29]

YEHUDAI, A. A hierarchy of real-time deterministic languages and their equivalence. 3. Comput. Syst. Sci. 24 (1982), 91-100.

Google Scholar

Cited By

View all

Zakharov V(2021)Efficient Equivalence Checking Technique for Some Classes of Finite-State MachinesAutomatic Control and Computer Sciences10.3103/S014641162107018X55:7(670-701)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.3103/S014641162107018X
Zakharov V(2020)Efficient Equivalence Checking Technique for Some Classes of Finite-State MachinesModeling and Analysis of Information Systems10.18255/1818-1015-2020-3-260-30327:3(260-303)Online publication date: 21-Sep-2020
https://doi.org/10.18255/1818-1015-2020-3-260-303
Böhm SGöller SJancar PBoneh DRoughgarden TFeigenbaum J(2013)Equivalence of deterministic one-counter automata is NL-completeProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488626(131-140)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488626
Show More Cited By

Index Terms

The equivalence problem for real-time DPDAs

Recommendations

Bisimulation equivalence and regularity for real-time one-counter automata

A one-counter automaton is a pushdown automaton with a singleton stack alphabet, where stack emptiness can be tested; it is a real-time automaton if it contains no ε-transitions. We study the computational complexity of the problems of equivalence and ...
Language equivalence of deterministic real-time one-counter automata is NL-complete
MFCS'11: Proceedings of the 36th international conference on Mathematical foundations of computer science

We prove that deciding language equivalence of deterministic realtime one-counter automata is NL-complete, in stark contrast to the inclusion problem which is known to be undecidable. This yields a subclass of deterministic pushdown automata for which ...
On the sizes of DPDAs, PDAs, LBAs

There are languages A such that there is a Pushdown Automata (PDA) that recognizes A which is much smaller than any Deterministic Pushdown Automata (DPDA) that recognizes A. There are languages A such that there is a Linear Bounded Automata (Linear ...

Reviews

Reviewer: Kazem Taghva

The decidability of the equivalence problem for the deterministic pushdown automata (DPDA) has been an important unresolved problem of language theory over the last three decades. A great deal of research has been focused on resolving this problem for the proper subclasses of DPDAs. A notable example is the decidability of the equivalence problem for LL(k) grammars [1]. Two of the well-known techniques for establishing positive results in these subclasses are Valiant's alternate stacking and parallel stacking [2]. In this paper, the author uses the parallel stacking technique to show that the equivalence problem for the real-time DPDAs (a real-time DPDA is a DPDA with no &egr;-move) is decidable. In addition, it is proved that the equivalence problem for two DPDAs is decidable if one of them is real-time. The paper is carefully written and contains some new ideas on the parallel stacking technique.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 34, Issue 3

July 1987

248 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/28869

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1987

Published in JACM Volume 34, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
677
Total Downloads

Downloads (Last 12 months)155
Downloads (Last 6 weeks)7

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zakharov V(2021)Efficient Equivalence Checking Technique for Some Classes of Finite-State MachinesAutomatic Control and Computer Sciences10.3103/S014641162107018X55:7(670-701)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.3103/S014641162107018X
Zakharov V(2020)Efficient Equivalence Checking Technique for Some Classes of Finite-State MachinesModeling and Analysis of Information Systems10.18255/1818-1015-2020-3-260-30327:3(260-303)Online publication date: 21-Sep-2020
https://doi.org/10.18255/1818-1015-2020-3-260-303
Böhm SGöller SJancar PBoneh DRoughgarden TFeigenbaum J(2013)Equivalence of deterministic one-counter automata is NL-completeProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488626(131-140)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488626
Böhm SGöller S(2011)Language equivalence of deterministic real-time one-counter automata is NL-completeProceedings of the 36th international conference on Mathematical foundations of computer science10.5555/2034006.2034028(194-205)Online publication date: 22-Aug-2011
https://dl.acm.org/doi/10.5555/2034006.2034028
Böhm SGöller S(2011)Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-CompleteMathematical Foundations of Computer Science 201110.1007/978-3-642-22993-0_20(194-205)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22993-0_20
Meitus V(2007)Equivalence of deterministic pushdown automata revisitedCybernetics and Systems Analysis10.1007/s10559-007-0037-743:2(179-191)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.1007/s10559-007-0037-7
Sénizergues G(2005)The Bisimulation Problem for Equational Graphs of Finite Out-DegreeSIAM Journal on Computing10.1137/S009753970037725634:5(1025-1106)Online publication date: Jan-2005
https://doi.org/10.1137/S0097539700377256
Sénizergues G(2005)The equivalence problem for deterministic pushdown automata is decidableAutomata, Languages and Programming10.1007/3-540-63165-8_221(671-681)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-63165-8_221
Culik K(2005)New techniques for proving the decidability of equivalence problemsAutomata, Languages and Programming10.1007/3-540-19488-6_114(162-175)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-19488-6_114
Sénizergues G(2002)L(A)=L(B)? A simplified decidability proofTheoretical Computer Science10.5555/2780683.2780843281:1(555-608)Online publication date: 3-Jun-2002
https://dl.acm.org/doi/10.5555/2780683.2780843
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Bisimulation equivalence and regularity for real-time one-counter automata

Language equivalence of deterministic real-time one-counter automata is NL-complete

On the sizes of DPDAs, PDAs, LBAs

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations