Document Open Access Logo

The Complexity of Separation for Levels in Concatenation Hierarchies

Authors Thomas Place, Marc Zeitoun

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.47.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

Thomas Place
  • LaBRI Bordeaux University and IUF, France
Marc Zeitoun
  • LaBRI Bordeaux University, France

Funding

Both authors acknowledge support from the DeLTA project (ANR-16-CE40-0007).

Cite As Get BibTex

Thomas Place and Marc Zeitoun. The Complexity of Separation for Levels in Concatenation Hierarchies. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2018.47

Abstract

We investigate the complexity of the separation problem associated to classes of regular languages. For a class C, C-separation takes two regular languages as input and asks whether there exists a third language in C which includes the first and is disjoint from the second. First, in contrast with the situation for the classical membership problem, we prove that for most classes C, the complexity of C-separation does not depend on how the input languages are represented: it is the same for nondeterministic finite automata and monoid morphisms. Then, we investigate specific classes belonging to finitely based concatenation hierarchies. It was recently proved that the problem is always decidable for levels 1/2 and 1 of any such hierarchy (with inefficient algorithms). Here, we build on these results to show that when the alphabet is fixed, there are polynomial time algorithms for both levels. Finally, we investigate levels 3/2 and 2 of the famous Straubing-Thérien hierarchy. We show that separation is PSpace-complete for level 3/2 and between PSpace-hard and EXPTime for level 2.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Regular languages
  • separation
  • concatenation hierarchies
  • complexity

Metrics

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

Related Versions

References

  1. Janusz A. Brzozowski and Rina S. Cohen. Dot-Depth of Star-Free Events. Journal of Computer and System Sciences, 5(1):1-16, 1971. Google Scholar
  2. Sang Cho and Dung T. Huynh. Finite automaton aperiodicity is PSPACE-complete. Theoretical Computer Science, 88(1):99-116, 1991. Google Scholar
  3. Wojciech Czerwiński, Wim Martens, and Tomáš Masopust. Efficient Separability of Regular Languages by Subsequences and Suffixes. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP'13), pages 150-161. Springer-Verlag, 2013. Google Scholar
  4. James Alexander Green. On the Structure of Semigroups. Annals of Mathematics, 54(1):163-172, 1951. Google Scholar
  5. Tomás Masopust. Separability by piecewise testable languages is PTIME-complete. Theoretical Computer Science, 711:109-114, 2018. Google Scholar
  6. Jean-Éric Pin. The Dot-Depth Hierarchy, 45 Years Later. In The Role of Theory in Computer Science - Essays Dedicated to Janusz Brzozowski, pages 177-202, 2017. Google Scholar
  7. Jean-Éric Pin. Mathematical Foundations of Automata Theory. In preparation, 2018. URL: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf.
  8. Jean-Eric Pin and Howard Straubing. Monoids of upper triangular Boolean matrices. In Semigroups. Structure and Universal Algebraic Problems, volume 39 of Colloquia Mathematica Societatis Janos Bolyal, pages 259-272. North-Holland, 1985. Google Scholar
  9. Thomas Place. Separating Regular Languages with Two Quantifier Alternations. Unpublished, a preliminary version can be found at https://arxiv.org/abs/1707.03295, 2018.
  10. Thomas Place, Lorijn van Rooijen, and Marc Zeitoun. Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages. In Proceedings of the 33rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'13, pages 363-375, Dagstuhl, Germany, 2013. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  11. Thomas Place, Lorijn van Rooijen, and Marc Zeitoun. Separating Regular Languages by Piecewise Testable and Unambiguous Languages. In Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS'13, pages 729-740. Springer-Verlag, 2013. Google Scholar
  12. Thomas Place and Marc Zeitoun. Separating Regular Languages with First-order Logic. In Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL'14) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'14), pages 75:1-75:10. ACM, 2014. Google Scholar
  13. Thomas Place and Marc Zeitoun. The tale of the quantifier alternation hierarchy of first-order logic over words. SIGLOG News, 2(3):4-17, 2015. Google Scholar
  14. Thomas Place and Marc Zeitoun. Separating Regular Languages with First-Order Logic. Logical Methods in Computer Science, 12(1), 2016. Google Scholar
  15. Thomas Place and Marc Zeitoun. Adding successor: A transfer theorem for separation and covering. Unpublished, a preliminary version can be found at http://arxiv.org/abs/1709.10052, 2017.
  16. Thomas Place and Marc Zeitoun. Going higher in the First-order Quantifier Alternation Hierarchy on Words. Unpublished, a preliminary version can be found at https://arxiv.org/abs/1404.6832, 2017.
  17. Thomas Place and Marc Zeitoun. Separation for Dot-depth Two. In Proceedings of the 32th Annual ACM/IEEE Symposium on Logic in Computer Science, (LICS'17), pages 202-213. IEEE Computer Society, 2017. Google Scholar
  18. Thomas Place and Marc Zeitoun. Generic results for concatenation hierarchies. Theory of Computing Systems (ToCS), 2018. Selected papers from CSR'17. Google Scholar
  19. Marcel Paul Schützenberger. On Finite Monoids Having Only Trivial Subgroups. Information and Control, 8:190-194, 1965. Google Scholar
  20. Imre Simon. Piecewise testable events. In 2nd GI Conference on Automata Theory and Formal Languages, pages 214-222, 1975. Google Scholar
  21. Howard Straubing. A Generalization of the Schützenberger Product of Finite Monoids. Theoretical Computer Science, 13(2):137-150, 1981. Google Scholar
  22. Denis Thérien. Classification of Finite Monoids: The Language Approach. Theoretical Computer Science, 14(2):195-208, 1981. 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