%0 Conference Proceedings
%T State Complexity of Unambiguous Operations on Deterministic Finite Automata
%+ Slovak Academy of Sciences (SAS)
%+ St Petersburg State University (SPbU)
%A Jirásková, Galina
%A Okhotin, Alexander
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 20th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Halifax, NS, Canada
%Y Stavros Konstantinidis
%Y Giovanni Pighizzini
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10952
%P 188-199
%8 2018-07-25
%D 2018
%R 10.1007/978-3-319-94631-3_16
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01905641/document
%2 https://inria.hal.science/hal-01905641/file/470153_1_En_16_Chapter.pdf
%L hal-01905641
%U https://inria.hal.science/hal-01905641
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10952