Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
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


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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


Files downloads