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

KUNC, Michal and Alexander OKHOTIN. State complexity of operations on two-way finite automata over a unary alphabet. Theoretical Computer Science. Amsterdam: Elsevier, 2012, vol. 449, No 1, p. 106-118. ISSN 0304-3975. Available from: https://dx.doi.org/10.1016/j.tcs.2012.04.010.

Basic information

• Original name: State complexity of operations on two-way finite automata over a unary alphabet
• Name in Czech: Stavová složitost operací na dvoucestných konečných automatech nad unární abecedou
• Authors: KUNC, Michal (203 Czech Republic, guarantor, belonging to the institution) and Alexander OKHOTIN (643 Russian Federation).
• Edition: Theoretical Computer Science, Amsterdam, Elsevier, 2012, 0304-3975.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10101 Pure mathematics
• Country of publisher: Netherlands
• Confidentiality degree: is not subject to a state or trade secret
• Impact factor: Impact factor: 0.489
• RIV identification code: RIV/00216224:14310/12:00057833
• Organization unit: Faculty of Science
• Doi: http://dx.doi.org/10.1016/j.tcs.2012.04.010
• UT WoS: 000306771300010
• Keywords (in Czech): Konečné automaty; Dvoucestné automaty; Regulární jazyky; Unární jazyky; Stavová složitost; Landauova funkce
• Keywords in English: Finite automata; Two-way automata; Regular languages; Unary languages; State complexity; Landau's function
• Tags: AKR, rivok
• Tags: International impact, Reviewed

Abstract

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.

Abstract (in Czech)

Č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ů.

Links

• GBP202/12/G061, research and development project: Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)

Investor: Czech Science Foundation