---
res:
  bibo_abstract:
  - In the Intersection Non-emptiness problem, we are given a list of finite automata
    A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine
    whether some string w ∈ Σ^* lies in the intersection of the languages accepted
    by the automata in the list. We analyze the complexity of the Intersection Non-emptiness
    problem under the promise that all input automata accept a language in some level
    of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy.
    Automata accepting languages from the lowest levels of these hierarchies arise
    naturally in the context of model checking. We identify a dichotomy in the dot-depth
    hierarchy by showing that the problem is already NP-complete when all input automata
    accept languages of the levels B_0 or B_{1/2} and already PSPACE-hard when all
    automata accept a language from the level B_1. Conversely, we identify a tetrachotomy
    in the Straubing-Thérien hierarchy. More precisely, we show that the problem is
    in AC^0 when restricted to level L_0; complete for L or NL, depending on the input
    representation, when restricted to languages in the level L_{1/2}; NP-complete
    when the input is given as DFAs accepting a language in L_1 or L_{3/2}; and finally,
    PSPACE-complete when the input automata accept languages in level L_2 or higher.
    Moreover, we show that the proof technique used to show containment in NP for
    DFAs accepting languages in L_1 or L_{3/2} does not generalize to the context
    of NFAs. To prove this, we identify a family of languages that provide an exponential
    separation between the state complexity of general NFAs and that of partially
    ordered NFAs. To the best of our knowledge, this is the first superpolynomial
    separation between these two models of computation.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Emmanuel
      foaf_name: Arrighi, Emmanuel
      foaf_surname: Arrighi
  - foaf_Person:
      foaf_givenName: Henning
      foaf_name: Fernau, Henning
      foaf_surname: Fernau
  - foaf_Person:
      foaf_givenName: Stefan
      foaf_name: Hoffmann, Stefan
      foaf_surname: Hoffmann
  - foaf_Person:
      foaf_givenName: Markus
      foaf_name: Holzer, Markus
      foaf_surname: Holzer
  - 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: Mateus
      foaf_name: De Oliveira Oliveira, Mateus
      foaf_surname: De Oliveira Oliveira
  - foaf_Person:
      foaf_givenName: Petra
      foaf_name: Wolf, Petra
      foaf_surname: Wolf
  bibo_doi: 10.4230/LIPIcs.FSTTCS.2021.34
  bibo_volume: 213
  dct_date: 2021^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/978-3-9597-7215-0
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: On the complexity of intersection non-emptiness for star-free language
    classes@
...