TY - GEN

T1 - State complexity of unambiguous operations on deterministic finite automata

AU - Jirásková, Galina

AU - Okhotin, Alexander

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The paper determines the number of states in a deterministic finite automaton (DFA) 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 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 3/8 2n+1. In the case of a unary alphabet, disjoint union requires up to 1/2 mn states, unambiguous concatenation has state complexity m + n-2, and unambiguous star requires n-2 states in the worst case.

AB - The paper determines the number of states in a deterministic finite automaton (DFA) 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 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 3/8 2n+1. In the case of a unary alphabet, disjoint union requires up to 1/2 mn states, unambiguous concatenation has state complexity m + n-2, and unambiguous star requires n-2 states in the worst case.

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

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

U2 - 10.1007/978-3-319-94631-3_16

DO - 10.1007/978-3-319-94631-3_16

M3 - Conference contribution

AN - SCOPUS:85050610342

SN - 9783319946306

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 188

EP - 199

BT - Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings

PB - Springer Nature

T2 - 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018

Y2 - 25 July 2018 through 27 July 2018

ER -