State complexity of operations on two-way finite automata over a unary alphabet

KUNC, Michal a Alexander OKHOTIN. State complexity of operations on two-way finite automata over a unary alphabet. Theoretical Computer Science. Amsterdam: Elsevier, 2012, roč. 449, č. 1, s. 106-118. ISSN 0304-3975. Dostupné z: https://dx.doi.org/10.1016/j.tcs.2012.04.010.

Zá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

• Originální 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
• Doi: http://dx.doi.org/10.1016/j.tcs.2012.04.010
• 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
• Štítky: AKR, rivok
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Anotace č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: Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky