Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F10%3A86075823" target="_blank" >RIV/61989100:27240/10:86075823 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
Popis výsledku v původním jazyce
Chrobak (1986) proved that a language accepted by a given nondeterministic finite automaton with one-letter alphabet, i.e., a unary NFA, with n states can be represented as the union of O(n(2)) arithmetic progressions, and Martinez (2002) has shown how to compute these progressions in polynomial time. To (2009) has pointed out recently that Chrobak's construction and Martinez's algorithm, which is based on it, contain a subtle error and has shown how they can be corrected. In this paper, a new simpler and more efficient algorithm for the same problem is presented. The running time of the presented algorithm is O(n(2)(n+m)), where n is the number of states and m the number of transitions of a given unary NFA.
Název v anglickém jazyce
Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
Popis výsledku anglicky
Chrobak (1986) proved that a language accepted by a given nondeterministic finite automaton with one-letter alphabet, i.e., a unary NFA, with n states can be represented as the union of O(n(2)) arithmetic progressions, and Martinez (2002) has shown how to compute these progressions in polynomial time. To (2009) has pointed out recently that Chrobak's construction and Martinez's algorithm, which is based on it, contain a subtle error and has shown how they can be corrected. In this paper, a new simpler and more efficient algorithm for the same problem is presented. The running time of the presented algorithm is O(n(2)(n+m)), where n is the number of states and m the number of transitions of a given unary NFA.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/1M0567" target="_blank" >1M0567: Centrum aplikované kybernetiky</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2010
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
Reachability Problems
ISBN
978-3-642-15348-8
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
7
Strana od-do
—
Název nakladatele
Springer-Verlag Berlin Heidelberg
Místo vydání
Berlin Heidelberg
Místo konání akce
Brno, Česká republika
Datum konání akce
28. 8. 2010
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000283104200012