2012
State complexity of operations on two-way finite automata over a unary alphabet
KUNC, Michal a Alexander OKHOTINZákladní údaje
Originální název
State complexity of operations on two-way finite automata over a unary alphabet
Název česky
Stavová složitost operací na dvoucestných konečných automatech nad unární abecedou
Autoři
KUNC, Michal (203 Česká republika, garant, domácí) a Alexander OKHOTIN (643 Rusko)
Vydání
Theoretical Computer Science, Amsterdam, Elsevier, 2012, 0304-3975
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.489
Kód RIV
RIV/00216224:14310/12:00057833
Organizační jednotka
Přírodovědecká fakulta
UT WoS
000306771300010
Klíčová slova česky
Konečné automaty; Dvoucestné automaty; Regulární jazyky; Unární jazyky; Stavová složitost; Landauova funkce
Klíčová slova anglicky
Finite automata; Two-way automata; Regular languages; Unary languages; State complexity; Landau's function
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 11. 4. 2013 18:00, Ing. Andrea Mikešková
V originále
The paper determines the number of states in two-way deterministic finite automata (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of basic language-theoretic operations on 2DFAs with a certain number of states. It is proved that (i) intersection of an m-state 2DFA and an n-state 2DFA requires between m+n and m+n+1 states; (ii) union of an m-state 2DFA and an n-state 2DFA, between m+n and 2m+n+4 states; (iii) Kleene star of an n-state 2DFA, (g(n)+O(n))^2 states, where g is Landau's function; (iv) k-th power of an n-state 2DFA, between (k-1)g(n)-k and k(g(n)+n) states; (v) concatenation of an m-state 2DFA and an n-state 2DFA, exp((1+O(1))sqrt((m+n)ln(m+n))) states. It is furthermore demonstrated that the Kleene star of a two-way nondeterministic automaton (2NFA) with n states requires Theta(g(n)) states in the worst case, its k-th power requires (k g(n))^(Theta(1)) states, and the concatenation of an m-state 2NFA and an n-state 2NFA, exp(Theta(sqrt((m+n)ln(m+n)))) states.
Česky
Článek určuje počet stavů dvoucestných deterministických konečných automatů (2DFA) nad jednopísmennou abecedou dostatečný a v nejhorším případě nutný pro reprezentování výsledků základních operací s formálními jazyky zadanými pomocí 2DFA s jistým počtem stavů. Je dokázáno, že (i) průnik 2DFA o m stavech a 2DFA o n stavech vyžaduje mezi m+n a m+n+1 stavy; (ii) sjednocení 2DFA o m stavech a 2DFA o n stavech mezi m+n a 2m+n+4 stavy; (iii) Kleeneho hvězdička 2DFA o n stavech (g(n)+O(n))^2 stavů, kde g je Landauova funkce; (iv) k-tá mocnina n-stavového 2DFA mezi (k-1)g(n)-k a k(g(n)+n) stavy; (v) zřetězení 2DFA o m stavech a 2DFA o n stavech exp((1+O(1))sqrt((m+n)ln(m+n))) stavů. Navíc je dokázáno, že Kleeneho hvězdička dvoucestného nedeterministického automatu (2NFA) o n stavech vyžaduje v nejhorším případě Theta(g(n)) stavů, jeho k-tá mocnina vyžaduje (k g(n))^(Theta(1)) stavů a zřetězení 2NFA o m stavech a 2NFA o n stavech exp(Theta(sqrt((m+n)ln(m+n)))) stavů.
Návaznosti
| GBP202/12/G061, projekt VaV |
|