Equivalence of deterministic one-counter automata is NL-complete
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F13%3A86088897" target="_blank" >RIV/61989100:27240/13:86088897 - isvavai.cz</a>
Result on the web
<a href="http://dl.acm.org/citation.cfm?id=2488608" target="_blank" >http://dl.acm.org/citation.cfm?id=2488608</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/2488608.2488626" target="_blank" >10.1145/2488608.2488626</a>
Alternative languages
Result language
angličtina
Original language name
Equivalence of deterministic one-counter automata is NL-complete
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F11%2F0340" target="_blank" >GAP202/11/0340: Modelling and verification of parallel systems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Annual ACM Symposium on Theory of Computing 2013
ISBN
978-1-4503-2029-0
ISSN
0737-8017
e-ISSN
—
Number of pages
10
Pages from-to
131-140
Publisher name
ACM
Place of publication
Seattle, WA
Event location
Palo Alto
Event date
Jun 1, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—