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 OKHOTIN Alexander

Druh Článek v odborném periodiku
Časopis / Zdroj Theoretical Computer Science
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Doi http://dx.doi.org/10.1016/j.tcs.2012.04.010
Obor Obecná matematika
Klíčová slova Finite automata; Two-way automata; Regular languages; Unary languages; State complexity; Landau's function
Popis Č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ů.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.