Document Open Access Logo

On the Complexity of Intersection Non-emptiness for Star-Free Language Classes

Authors Emmanuel Arrighi , Henning Fernau , Stefan Hoffmann , Markus Holzer , Ismaël Jecker , Mateus de Oliveira Oliveira , Petra Wolf

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.34.pdf
  • Filesize: 0.8 MB
  • 15 pages

Document Identifiers

Author Details

Emmanuel Arrighi
  • University of Bergen, Norway
Henning Fernau
  • Fachbereich IV, Informatikwissenschaften, Universität Trier, Germany
Stefan Hoffmann
  • Fachbereich IV, Informatikwissenschaften, Universität Trier, Germany
Markus Holzer
  • Institut für Informatik, Universität Giessen, Germany
Ismaël Jecker
  • Institute of Science and Technology, Klosterneuburg, Austria
Mateus de Oliveira Oliveira
  • University of Bergen, Norway
Petra Wolf
  • Fachbereich IV, Informatikwissenschaften, Universität Trier, Germany

Funding

  • Arrighi, Emmanuel: Research Council of Norway (no. 274526), IS-DAAD (no. 309319).
  • Fernau, Henning: DAAD PPP (no. 57525246).
  • Jecker, Ismaël: Marie Skłodowska-Curie Grant Agreement no. 754411.
  • de Oliveira Oliveira, Mateus: Research Council of Norway (no. 288761), IS-DAAD (no. 309319).
  • Wolf, Petra: DFG project FE 560/9-1, DAAD PPP (no. 57525246).

Acknowledgements

We like to thank Lukas Fleischer and Michael Wehar for our discussions. This work started at the Schloss Dagstuhl Event 20483 Moderne Aspekte der Komplexitätstheorie in der Automatentheorie https://www.dagstuhl.de/20483.

Cite As Get BibTex

Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Mateus de Oliveira Oliveira, and Petra Wolf. On the Complexity of Intersection Non-emptiness for Star-Free Language Classes. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.FSTTCS.2021.34

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Intersection Non-emptiness Problem
  • Star-Free Languages
  • Straubing-Thérien Hierarchy
  • dot-depth Hierarchy
  • Commutative Languages
  • Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Parosh Aziz Abdulla. Regular model checking. International Journal on Software Tools for Technology Transfer, 14(2):109-118, 2012. Google Scholar
  2. Jorge Almeida and Ondrej Klíma. New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages. Discrete Mathematics & Theoretical Computer Science, 12(4):41-58, 2010. Google Scholar
  3. Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Mateus de Oliveira Oliveira, and Petra Wolf. On the Complexity of Intersection Non-emptiness for Star-Free Language Classes. CoRR, abs/2110.01279, 2021. URL: http://arxiv.org/abs/2110.01279,
  4. Ahmed Bouajjani, Bengt Jonsson, Marcus Nilsson, and Tayssir Touili. Regular model checking. In E. Allen Emerson and A. Prasad Sistla, editors, Computer Aided Verification, 12th International Conference, CAV, volume 1855 of Lecture Notes in Computer Science, pages 403-418. Springer, 2000. Google Scholar
  5. Ahmed Bouajjani, Anca Muscholl, and Tayssir Touili. Permutation rewriting and algorithmic verification. Information and Computation, 205:199-224, 2007. Google Scholar
  6. Janusz A. Brzozowski. Hierarchies of aperiodic languages. RAIRO Informatique théorique et Applications/Theoretical Informatics and Applications, 10(2):33-49, 1976. Google Scholar
  7. Janusz A. Brzozowski and Faith E. Fich. Languages of ℛ-trivial monoids. Journal of Computer and System Sciences, 20(1):32-49, February 1980. Google Scholar
  8. Janusz A. Brzozowski and Robert Knast. The dot-depth hierarchy of star-free languages is infinite. Journal of Computer and System Sciences, 16(1):37-55, 1978. Google Scholar
  9. Sang Cho and Dung T. Huynh. Finite-automaton aperiodicity is PSPACE-complete. Theoretical Computer Science, 88(1):99-116, September 1991. Google Scholar
  10. Marek Chrobak. Finite automata and unary languages. Theoretical Computer Science, 47(3):149-158, 1986. Google Scholar
  11. Rina S. Cohen and Janusz A. Brzozowski. Dot-depth of star-free events. Journal of Computer and System Sciences, 5(1):1-16, 1971. Google Scholar
  12. Henning Fernau and Andreas Krebs. Problems on finite automata and the exponential time hypothesis. Algorithms, 10(1):24, 2017. Google Scholar
  13. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  14. Pawel Gawrychowski. Chrobak normal form revisited, with applications. In Béatrice Bouchou-Markhoff, Pascal Caron, Jean-Marc Champarnaud, and Denis Maurel, editors, Implementation and Application of Automata - 16th International Conference, CIAA, volume 6807 of Lecture Notes in Computer Science, pages 142-153. Springer, 2011. Google Scholar
  15. Christian Glaßer and Heinz Schmitz. Decidable hierarchies of starfree languages. In Sanjiv Kapoor and Sanjiva Prasad, editors, Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS, volume 1974 of Lecture Notes in Computer Science, pages 503-515. Springer, 2000. Google Scholar
  16. Christian Glaßer and Heinz Schmitz. Level 5/2 of the Straubing-Thérien hierarchy for two-letter alphabets. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory, 5th International Conference, DLT, volume 2295 of Lecture Notes in Computer Science, pages 251-261. Springer, 2001. Google Scholar
  17. Juris Hartmanis, Neil Immerman, and Stephen R. Mahaney. One-way log-tape reductions. In 19th Annual Symposium on Foundations of Computer Science, FOCS, pages 65-72. IEEE Computer Society, 1978. Google Scholar
  18. Stefan Hoffmann. Regularity conditions for iterated shuffle on commutative regular languages. accepted at CIAA, 2021. Google Scholar
  19. Harry B. Hunt III and Daniel J. Rosenkrantz. Computational parallels between the regular and context-free languages. SIAM Journal on Computing, 7(1):99-114, 1978. Google Scholar
  20. George Karakostas, Richard J. Lipton, and Anastasios Viglas. On the complexity of intersecting finite state automata and NL versus NP. Theoretical Computer Science, 302(1):257-274, 2003. Google Scholar
  21. Takumi Kasai and Shigeki Iwata. Gradually intractable problems and nondeterministic log-space lower bounds. Mathematical Systems Theory, 18(1):153-170, 1985. Google Scholar
  22. Felix Klein and Martin Zimmermann. How much lookahead is needed to win infinite games? Logical Methods in Computer Science, 12(3), 2016. URL: https://doi.org/10.2168/LMCS-12(3:4)2016.
  23. Ondrej Klíma and Libor Polák. Subhierarchies of the second level in the straubing-thérien hierarchy. International Journal of Algebra and Computation, 21(7):1195-1215, 2011. Google Scholar
  24. Dexter Kozen. Lower bounds for natural proof systems. In 18th Annual Symposium on Foundations of Computer Science, FOCS, pages 254-266. IEEE Computer Society, 1977. Google Scholar
  25. Markus Krötsch, Tomás Masopust, and Michaël Thomazo. Complexity of universality and related problems for partially ordered NFAs. Information and Computation, 255:177-192, 2017. Google Scholar
  26. Klaus-Jörn Lange and Peter Rossmanith. The emptiness problem for intersections of regular languages. In Ivan M. Havel and Václav Koubek, editors, Mathematical Foundations of Computer Science 1992, 17th International Symposium, MFCS, volume 629 of Lecture Notes in Computer Science, pages 346-354. Springer, 1992. Google Scholar
  27. Tomás Masopust. Separability by piecewise testable languages is PTime-complete. Theoretical Computer Science, 711:109-114, 2018. Google Scholar
  28. Tomás Masopust and Markus Krötzsch. Partially ordered automata and piecewise testability. CoRR, abs/1907.13115, 2019. URL: http://arxiv.org/abs/1907.13115.
  29. Tomás Masopust and Michaël Thomazo. On the complexity of k-piecewise testability and the depth of automata. In Igor Potapov, editor, Developments in Language Theory - 19th International Conference, DLT, number 9168 in Lecture Notes in Computer Science, pages 364-376. Springer, 2015. Google Scholar
  30. Mike Naylor. Abacaba! – using a mathematical pattern to connect art, music, poetry and literature. Bridges, pages 89-96, 2011. Google Scholar
  31. Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  32. Jean-Éric Pin. Bridges for concatenation hierarchies. In Kim Guldstrand Larsen, Sven Skyum, and Glynn Winskel, editors, Automata, Languages and Programming, 25th International Colloquium, ICALP, volume 1443 of Lecture Notes in Computer Science, pages 431-442. Springer, 1998. Google Scholar
  33. Thomas Place and Marc Zeitoun. Generic results for concatenation hierarchies. Theory of Computing Systems, 63(4):849-901, 2019. Google Scholar
  34. Narad Rampersad and Jeffrey Shallit. Detecting patterns in finite regular and context-free languages. Information Processing Letters, 110(3):108-112, 2010. Google Scholar
  35. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, 1970. Google Scholar
  36. Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8(2):190-194, 1965. Google Scholar
  37. Thomas Schwentick, Denis Thérien, and Heribert Vollmer. Partially-ordered two-way automata: A new characterization of DA. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory, 5th International Conference, DLT, volume 2295 of Lecture Notes in Computer Science, pages 239-250. Springer, 2001. Google Scholar
  38. Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In Alfred V. Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Harrison, Richard M. Karp, and H. Raymond Strong, editors, 5th Annual Symposium on Theory of Computing, STOC, pages 1-9. ACM, 1973. Google Scholar
  39. Howard Straubing. A generalization of the Schützenberger product of finite monoids. Theoretical Computer Science, 13:137-150, 1981. Google Scholar
  40. Howard Straubing. Finite semigroup varieties of the form V^* D. Journal of Pure and Applied Algebra, 36:53-94, 1985. Google Scholar
  41. Ivan Hal Sudborough. On tape-bounded complexity classes and multihead finite automata. Journal of Computer and System Sciences, 10(1):62-76, February 1975. Google Scholar
  42. Denis Thérien. Classification of finite monoids: the language approach. Theoretical Computer Science, 14(2):195-208, 1981. Google Scholar
  43. Todd Wareham. The parameterized complexity of intersection and composition operations on sets of finite-state automata. In Sheng Yu and Andrei Paun, editors, Implementation and Application of Automata, 5th International Conference, CIAA, volume 2088 of Lecture Notes in Computer Science, pages 302-310. Springer, 2000. Google Scholar
  44. Michael Wehar. Hardness results for intersection non-emptiness. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP, Part II, volume 8573 of Lecture Notes in Computer Science, pages 354-362. Springer, 2014. Google Scholar
  45. Michael Wehar. On the Complexity of Intersection Non-Emptiness Problems. PhD thesis, University at Buffalo, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact