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 metadatas

Cited literature [20 references]  Display  Hide  Download

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

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

58