---
res:
  bibo_abstract:
  - A regular language L of finite words is composite if there are regular languages
    L₁,L₂,…,L_t such that L = ⋂_{i = 1}^t L_i and the index (number of states in a
    minimal DFA) of every language L_i is strictly smaller than the index of L. Otherwise,
    L is prime. Primality of regular languages was introduced and studied in [O. Kupferman
    and J. Mosheiff, 2015], where the complexity of deciding the primality of the
    language of a given DFA was left open, with a doubly-exponential gap between the
    upper and lower bounds. We study primality for unary regular languages, namely
    regular languages with a singleton alphabet. A unary language corresponds to a
    subset of ℕ, making the study of unary prime languages closer to that of primality
    in number theory. We show that the setting of languages is richer. In particular,
    while every composite number is the product of two smaller numbers, the number
    t of languages necessary to decompose a composite unary language induces a strict
    hierarchy. In addition, a primality witness for a unary language L, namely a word
    that is not in L but is in all products of languages that contain L and have an
    index smaller than L’s, may be of exponential length. Still, we are able to characterize
    compositionality by structural properties of a DFA for L, leading to a LogSpace
    algorithm for primality checking of unary DFAs.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Ismael R
      foaf_name: Jecker, Ismael R
      foaf_surname: Jecker
      foaf_workInfoHomepage: http://www.librecat.org/personId=85D7C63E-7D5D-11E9-9C0F-98C4E5697425
  - foaf_Person:
      foaf_givenName: Orna
      foaf_name: Kupferman, Orna
      foaf_surname: Kupferman
  - foaf_Person:
      foaf_givenName: Nicolas
      foaf_name: Mazzocchi, Nicolas
      foaf_surname: Mazzocchi
  bibo_doi: 10.4230/LIPIcs.MFCS.2020.51
  bibo_volume: 170
  dct_date: 2020^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959771597
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Unary prime languages@
...