Equivalence of deterministic one-counter automata is NL-complete
Popis výsledku
Identifikátory výsledku
Kód výsledku v IS VaVaI
Výsledek na webu
DOI - Digital Object Identifier
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Equivalence of deterministic one-counter automata is NL-complete
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Equivalence of deterministic one-counter automata is NL-complete
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of the Annual ACM Symposium on Theory of Computing 2013
ISBN
978-1-4503-2029-0
ISSN
0737-8017
e-ISSN
—
Počet stran výsledku
10
Strana od-do
131-140
Název nakladatele
ACM
Místo vydání
Seattle, WA
Místo konání akce
Palo Alto
Datum konání akce
1. 6. 2013
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—
Druh výsledku
D - Stať ve sborníku
CEP
IN - Informatika
Rok uplatnění
2013