State complexity of unambiguous operations on deterministic finite automata

Galina Jirásková, Alexander Okhotin

Research output

1 Citation (Scopus)

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 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 3/8 2n+1. In the case of a unary alphabet, disjoint union requires up to 1/2 mn states, unambiguous concatenation has state complexity m + n-2, and unambiguous star requires n-2 states in the worst case.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings
PublisherSpringer
Pages188-199
Number of pages12
ISBN (Print)9783319946306
DOIs
Publication statusPublished - 1 Jan 2018
Event20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 - Halifax
Duration: 25 Jul 201827 Jul 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10952 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018
CountryCanada
CityHalifax
Period25/07/1827/07/18

    Fingerprint

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Jirásková, G., & Okhotin, A. (2018). State complexity of unambiguous operations on deterministic finite automata. In Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings (pp. 188-199). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10952 LNCS). Springer. https://doi.org/10.1007/978-3-319-94631-3_16