On the state and computational complexity of the reverse of acyclic minimal DFAs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F12%3A00379774" target="_blank" >RIV/67985840:_____/12:00379774 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-642-31606-7_20" target="_blank" >http://dx.doi.org/10.1007/978-3-642-31606-7_20</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-31606-7_20" target="_blank" >10.1007/978-3-642-31606-7_20</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the state and computational complexity of the reverse of acyclic minimal DFAs

Popis výsledku v původním jazyce

We study the state complexity of the reverse of acyclic minimal deterministic finite automata, and the computational complexity of the following problem: Given an acyclic minimal DFA, is the minimal DFA for the reverse also acyclic? Note that we allow self-loops in acyclic automata. We show that there exists a language accepted by an acyclic minimal DFA such that the minimal DFA for its reverse is exponential with respect to the number of states, and we establish a tight bound on the state complexity ofthe reverse of acyclic DFAs. We also give a direct proof of the fact that the minimal DFA for the reverse is acyclic if and only if the original acyclic minimal DFA satisfies a certain structural property, which can be tested in quadratic time.

Název v anglickém jazyce

On the state and computational complexity of the reverse of acyclic minimal DFAs

Popis výsledku anglicky

We study the state complexity of the reverse of acyclic minimal deterministic finite automata, and the computational complexity of the following problem: Given an acyclic minimal DFA, is the minimal DFA for the reverse also acyclic? Note that we allow self-loops in acyclic automata. We show that there exists a language accepted by an acyclic minimal DFA such that the minimal DFA for its reverse is exponential with respect to the number of states, and we establish a tight bound on the state complexity ofthe reverse of acyclic DFAs. We also give a direct proof of the fact that the minimal DFA for the reverse is acyclic if and only if the original acyclic minimal DFA satisfies a certain structural property, which can be tested in quadratic time.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GPP202%2F11%2FP028" target="_blank" >GPP202/11/P028: Decentralizované a koordinační supervizní řízení</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

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

Implementation and application of automata

ISBN

978-3-642-31605-0

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

229-239

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Porto

Datum konání akce

17. 7. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—