Equivalence of deterministic one-counter automata is NL-complete

Popis výsledku

—

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.

Projekt
GAP202/11/0340: Modelování a verifikace paralelních systémů
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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ů

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