article

Deterministic one-counter automata

Authors:

Leslie G. Valiant,

Michael S. PatersonAuthors Info & Claims

Journal of Computer and System Sciences, Volume 10, Issue 3

Pages 340 - 350

https://doi.org/10.1016/S0022-0000(75)80005-5

Published: 01 June 1975 Publication History

Abstract

The equivalence problem for deterministic one-counter automata is shown to bedecidable. A corollary for schema theory is that equivalence is decidable for Ianov schemas with an auxiliary counter.

References

[1]

In: Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, MA.

Crossref

Google Scholar

[2]

In: Handbuch der Lehre von der Verteilung der Primzahlen, Teubner, Leipzig und Berlin.

Google Scholar

[3]

In: Computation: Finite and Infinite Machines, Prentice-Hall, Englewood Cliffs, NJ.

Crossref

Google Scholar

[4]

Decision problems in computational models. In: Proc. ACM Conference on Proving Assertions about Programs,

Crossref

Google Scholar

[5]

Properties of deterministic top-down grammars. Information and Control. v17. 226-256.

Google Scholar

[6]

Decision procedures for families of deterministic pushdown automata. In: Ph.D. Thesis., Report No. 7, University of Warwick Computer Centre.

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
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
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
Show More Cited By

Deterministic one-counter automata
1. Theory of computation

Recommendations

Quantum versus deterministic counter automata

This paper focuses on quantum analogues of various models of counter automata, and almost completely proves the relation between the classes of languages recognizable by bounded error quantum ones and classical deterministic ones in every model of ...
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 ...
Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata

We investigate the conversion of one-way nondeterministic finite automata and context-free grammars into Parikh equivalent one-way and two-way deterministic finite automata, from a descriptional complexity point of view. We prove that for each one-way ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 10, Issue 3

June, 1975

112 pages

ISSN:0022-0000

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 June 1975

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 24 Nov 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
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
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
Englert MLazić RTotzke PKoskinen EGrohe MShankar N(2016)Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-CompleteProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/2933575.2933577(477-484)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1145/2933575.2933577
Blondin MFinkel AGoller SHaase CMcKenzie P(2015)Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-CompleteProceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS.2015.14(32-43)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1109/LICS.2015.14
Mallet Fde Simone R(2015)Correctness issues on MARTE/CCSL constraintsScience of Computer Programming10.1016/j.scico.2015.03.001106:C(78-92)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.scico.2015.03.001
Böhm SGöller SJančar P(2014)Bisimulation equivalence and regularity for real-time one-counter automataJournal of Computer and System Sciences10.1016/j.jcss.2013.11.00380:4(720-743)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1016/j.jcss.2013.11.003
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 SJančar P(2010)Bisimilarity of one-counter processes is PSPACE-completeProceedings of the 21st international conference on Concurrency theory10.5555/1887654.1887667(177-191)Online publication date: 31-Aug-2010
https://dl.acm.org/doi/10.5555/1887654.1887667
Show More Cited By

View Options

View options

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

Recommendations

Quantum versus deterministic counter automata

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

Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations