# State Complexity of Unambiguous Operations on Deterministic Finite Automata

Abstract : 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 $m2^{n-1} - 2^{n-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 $\frac{3}{8}2^n+1$. In the case of a unary alphabet, disjoint union requires up to $\frac{1}{2}mn$ states, unambiguous concatenation has state complexity $m+n-2$, and unambiguous star requires $n-2$ states in the worst case.
Document type :
Conference papers
Domain :

Cited literature [21 references]

https://hal.inria.fr/hal-01905641
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:48 AM
Last modification on : Friday, October 26, 2018 - 8:05:05 AM
Long-term archiving on: : Sunday, January 27, 2019 - 12:45:53 PM

### File

470153_1_En_16_Chapter.pdf
Files produced by the author(s)

### Citation

Galina Jirásková, Alexander Okhotin. State Complexity of Unambiguous Operations on Deterministic Finite Automata. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.188-199, ⟨10.1007/978-3-319-94631-3_16⟩. ⟨hal-01905641⟩

Record views