State complexity of unambiguous operations on finite automata

Galina Jirásková, Alexander Okhotin

Research output

Abstract

The paper determines the number of states in finite automata 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 deterministic finite automata (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 [Formula presented]. In the case of a unary alphabet, disjoint union requires up to [Formula presented] states in a DFA, unambiguous concatenation has state complexity m+n−2, and unambiguous star requires n−2 states in the worst case. For nondeterministic finite automata, as well as for unambiguous finite automata, the complexity for disjoint union is m+n, for unambiguous concatenation, square, and star, the resulting complexities are m+n, 2n, and n+1, respectively, and all of them are witnessed by binary languages. In the unary nondeterministic or unambiguous case, the corresponding complexities are m+n for disjoint union, m+n−1 and 2n−1 for unambiguous concatenation and square, respectively, and n−1 for unambiguous star.

Original languageEnglish
Pages (from-to)52-64
JournalTheoretical Computer Science
Volume798
DOIs
Publication statusPublished - 17 Dec 2019

    Fingerprint

Scopus subject areas

  • Theoretical Computer Science

Cite this