TY - JOUR

T1 - State complexity of unambiguous operations on finite automata

AU - Jirásková, Galina

AU - Okhotin, Alexander

PY - 2019/12/17

Y1 - 2019/12/17

N2 - The paper determines the number of states in finite automata necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state deterministic finite automata (DFA), the state complexity is mn−1; for the unambiguous concatenation, it is known to be m2n−1−2n−2 (Daley et al., “Orthogonal concatenation: language equations and state complexity”, J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be [Formula presented]. In the case of a unary alphabet, disjoint union requires up to [Formula presented] states in a DFA, unambiguous concatenation has state complexity m+n−2, and unambiguous star requires n−2 states in the worst case. For nondeterministic finite automata, as well as for unambiguous finite automata, the complexity for disjoint union is m+n, for unambiguous concatenation, square, and star, the resulting complexities are m+n, 2n, and n+1, respectively, and all of them are witnessed by binary languages. In the unary nondeterministic or unambiguous case, the corresponding complexities are m+n for disjoint union, m+n−1 and 2n−1 for unambiguous concatenation and square, respectively, and n−1 for unambiguous star.

AB - The paper determines the number of states in finite automata necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state deterministic finite automata (DFA), the state complexity is mn−1; for the unambiguous concatenation, it is known to be m2n−1−2n−2 (Daley et al., “Orthogonal concatenation: language equations and state complexity”, J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be [Formula presented]. In the case of a unary alphabet, disjoint union requires up to [Formula presented] states in a DFA, unambiguous concatenation has state complexity m+n−2, and unambiguous star requires n−2 states in the worst case. For nondeterministic finite automata, as well as for unambiguous finite automata, the complexity for disjoint union is m+n, for unambiguous concatenation, square, and star, the resulting complexities are m+n, 2n, and n+1, respectively, and all of them are witnessed by binary languages. In the unary nondeterministic or unambiguous case, the corresponding complexities are m+n for disjoint union, m+n−1 and 2n−1 for unambiguous concatenation and square, respectively, and n−1 for unambiguous star.

KW - Disjoint union

KW - State complexity

KW - Unambiguous concatenation

KW - Unambiguous star

KW - CONCATENATION

KW - BASIC OPERATIONS

UR - http://www.scopus.com/inward/record.url?scp=85066100783&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/state-complexity-unambiguous-operations-finite-automata

U2 - 10.1016/j.tcs.2019.04.008

DO - 10.1016/j.tcs.2019.04.008

M3 - Article

AN - SCOPUS:85066100783

VL - 798

SP - 52

EP - 64

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -