research-article

Equivalence of deterministic one-counter automata is NL-complete

Authors:

Stanislav Böhm,

Stefan Göller,

Petr JancarAuthors Info & Claims

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

Pages 131 - 140

https://doi.org/10.1145/2488608.2488626

Published: 01 June 2013 Publication History

Abstract

We prove that language equivalence of deterministic one-counter automata is NL-complete. This improves the superpolynomial time complexity upper bound shown by Valiant and Paterson in 1975. Our main contribution is to prove that two deterministic one-counter automata are inequivalent if and only if they can be distinguished by a word of length polynomial in the size of the two input automata.

References

[1]

P. Berman and R. Roos. Learning One-Counter Languages in Polynomial Time (Extended Abstract). In Proc. of FOCS, pages 61?-67. IEEE, 1987.

Digital Library

[2]

S. Bohm and S. Goller. Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete. In Proc. of MFCS, volume 6907 of Lecture Notes in Computer Science, pages 194?-205. Springer, 2011.

Digital Library

[3]

S. Bohm, S. Goller, and P. Jancar. Bisimilarity of one-counter processes is PSPACE-complete. In Proc. of CONCUR, volume 6269 of Lecture Notes in Computer Science, pages 177-?191. Springer, 2010.

Digital Library

[4]

W. Czerwi ?nski and S. Lasota. Fast equivalence-checking for normed context-free processes. In Proc. FSTTCS'10, volume 8 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010.

[5]

A. F. Fahmy and R. S. Roos. Efficient Learning of Real Time One-Counter Automata. In Proc. of ALT, volume 997 of Lecture Notes in Computer Science, pages 25?-40. Springer, 1995.

Digital Library

[6]

K. Higuchi, M. Wakatsuki, and E. Tomita. A polynomial-time algorithm for checking the inclusion for real-time deterministic restricted one-counter automata which accept by final state. IEICE Trans. Information and Systems, E78-D:939?-950, 1995.

[7]

K. Higuchi, M. Wakatsuki, and E. Tomita. A polynomial-time algorithm for checking the inclusion for real-time deterministic restricted one-counter automata which accept by accept mode. IEICE Trans. Information and Systems, E81-D:1-?11, 1998.

[8]

Y. Hirshfeld, M. Jerrum, and F. Moller. A Polynomial Algorithm for Deciding Bisimilarity of Normed Context-Free Processes. Theor. Comput. Sci., 158(1&2):143?-159, 1996.

Digital Library

[9]

P. Jancar. Decidability of dpda language equivalence via first-order grammars. In Proc. of LICS, pages 415-?424. IEEE, 2012.

Digital Library

[10]

P. Jancar, A. Ku?cera, and F. Moller. Simulation and bisimulation over one-counter processes. In Proc. of STACS, volume 1770 of Lecture Notes in Computer Science, pages 334-?345, 2000.

Digital Library

[11]

R. Mayr. Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes. In Proc. of ICALP, volume 2719 of Lecture Notes in Computer Science, pages 570?-583, 2003.

Digital Library

[12]

M. Oyamaguchi. The equivalence problem for real-time DPDAs. J. ACM, 34:731?-760, 1987.

Digital Library

[13]

R. Roos. Deciding Equivalence of Deterministic One-Counter Automata in Polynomial Time with Applications to Learning. PhD thesis, The Pennsylvania State University, 1988.

Digital Library

[14]

G. Senizergues. L(A)=L(B)? decidability results from complete formal systems. Theor. Comput. Sci., 251(1-2):1-?166, 2001.

Digital Library

[15]

G. Senizergues. L(A)=L(B)? A simplified decidability proof. Theor. Comput. Sci., 281(1-2):555-?608, 2002.

Digital Library

[16]

G. Senizergues. The Equivalence Problem for t-Turn DPDA Is Co-NP. In Proc. of ICALP, volume 2719 of Lecture Notes in Computer Science, pages 478?-489. Springer, 2003.

Digital Library

[17]

C. Stirling. Deciding DPDA Equivalence Is Primitive Recursive. In Proc. of ICALP, volume 2380 of Lecture Notes in Computer Science, pages 821?-832. Springer, 2002.

Digital Library

[18]

L. G. Valiant and M. Paterson. Deterministic one-counter automata. J. Comput. Syst. Sci., 10(3):340?-350, 1975.

Digital Library

Cited By

Prakash AThejaswini K(2023)On History-Deterministic One-Counter NetsFoundations of Software Science and Computation Structures10.1007/978-3-031-30829-1_11(218-239)Online publication date: 21-Apr-2023
https://doi.org/10.1007/978-3-031-30829-1_11
Gay SPoças DVasconcelos V(2022)The Different Shades of Infinite Session TypesFoundations of Software Science and Computation Structures10.1007/978-3-030-99253-8_18(347-367)Online publication date: 29-Mar-2022
https://doi.org/10.1007/978-3-030-99253-8_18
Blondin MEnglert MFinkel AGÖller SHaase CLazić RMckenzie PTotzke P(2021)The Reachability Problem for Two-Dimensional Vector Addition Systems with StatesJournal of the ACM10.1145/346479468:5(1-43)Online publication date: 12-Aug-2021
https://dl.acm.org/doi/10.1145/3464794
Show More Cited By

Index Terms

Equivalence of deterministic one-counter automata is NL-complete
1. Theory of computation
  1. Formal languages and automata theory

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 ...
Some properties of one-pebble turing machines with sublogarithmic space

This paper investigates some aspects of the accepting powers of deterministic, nondeterministic, and alternating one-pebble Turing machines with spaces between log log n and log n. We first investigate a relationship between the accepting powers of two-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

June 2013

998 pages

ISBN:9781450320290

DOI:10.1145/2488608

General Chairs:
Dan Boneh
Stanford University, USA
,
Tim Roughgarden
Stanford University, USA
,
Program Chair:
Joan Feigenbaum
Yale University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'13

Sponsor:

SIGACT

STOC'13: Symposium on Theory of Computing

June 1 - 4, 2013

California, Palo Alto, USA

Acceptance Rates

STOC '13 Paper Acceptance Rate 100 of 360 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
221
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Prakash AThejaswini K(2023)On History-Deterministic One-Counter NetsFoundations of Software Science and Computation Structures10.1007/978-3-031-30829-1_11(218-239)Online publication date: 21-Apr-2023
https://doi.org/10.1007/978-3-031-30829-1_11
Gay SPoças DVasconcelos V(2022)The Different Shades of Infinite Session TypesFoundations of Software Science and Computation Structures10.1007/978-3-030-99253-8_18(347-367)Online publication date: 29-Mar-2022
https://doi.org/10.1007/978-3-030-99253-8_18
Blondin MEnglert MFinkel AGÖller SHaase CLazić RMckenzie PTotzke P(2021)The Reachability Problem for Two-Dimensional Vector Addition Systems with StatesJournal of the ACM10.1145/346479468:5(1-43)Online publication date: 12-Aug-2021
https://dl.acm.org/doi/10.1145/3464794
Kutrib MMalcher AWendlandt M(2021)Input-driven multi-counter automataTheoretical Computer Science10.1016/j.tcs.2021.01.032870(121-136)Online publication date: May-2021
https://doi.org/10.1016/j.tcs.2021.01.032
Li XChen TWu ZXia M(2020)Computing Linear Arithmetic Representation of Reachability Relation of One-Counter AutomataDependable Software Engineering. Theories, Tools, and Applications10.1007/978-3-030-62822-2_6(89-107)Online publication date: 24-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-62822-2_6
Kutrib MMalcher AWendlandt M(2019)Input-Driven Multi-counter AutomataImplementation and Application of Automata10.1007/978-3-030-23679-3_16(197-208)Online publication date: 26-Jun-2019
https://doi.org/10.1007/978-3-030-23679-3_16
Jančar POsička PSawa Z(2018)EXPSPACE-Complete Variant of Countdown Games, and Simulation on Succinct One-Counter NetsReachability Problems10.1007/978-3-030-00250-3_5(59-74)Online publication date: 30-Aug-2018
https://doi.org/10.1007/978-3-030-00250-3_5
Atig MChistikov DHofman PKumar KSaivasan PZetzsche GKoskinen EGrohe MShankar N(2016)The complexity of regular abstractions of one-counter languagesProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/2933575.2934561(207-216)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1145/2933575.2934561
Mamouras K(2016)The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion SchemesACM Transactions on Computational Logic10.1145/283549117:2(1-30)Online publication date: 7-Jan-2016
https://dl.acm.org/doi/10.1145/2835491
Ibarra OSeki S(2015)Semilinear Sets and Counter MachinesFundamenta Informaticae10.5555/2756686.2756692138:1-2(61-76)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.5555/2756686.2756692
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents