Document Open Access Logo

On All Things Star-Free (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Thomas Place, Marc Zeitoun

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.126.pdf
  • Filesize: 491 kB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Regular languages
  • separation problem
  • star-free closure
  • group languages

Metrics

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

Abstract

We investigate the star-free closure, which associates to a class of languages its closure under Boolean operations and marked concatenation. We prove that the star-free closure of any finite class and of any class of groups languages with decidable separation (plus mild additional properties) has decidable separation. We actually show decidability of a stronger property, called covering. This generalizes many results on the subject in a unified framework. A key ingredient is that star-free closure coincides with another closure operator where Kleene stars are also allowed in restricted contexts.

Cite As Get BibTex

Thomas Place and Marc Zeitoun. On All Things Star-Free (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 126:1-126:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.126

Author Details

Thomas Place
  • Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence and IUF, France
Marc Zeitoun
  • Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence, France

Funding

DeLTA project (ANR-16-CE40-0007)

References

  1. Jorge Almeida. Some Algorithmic Problems for Pseudovarieties. Publicationes Mathematicae Debrecen, 54:531-552, 1999. Google Scholar
  2. Christopher J. Ash. Inevitable Graphs: a Proof of the Type II Conjecture and some Related Decision Procedures. IJAC, 1(1):127-146, 1991. Google Scholar
  3. David A. Mix Barrington, Kevin Compton, Howard Straubing, and Denis Thérien. Regular languages in NC1. Journal of Computer and System Sciences, 44(3):478-499, 1992. Google Scholar
  4. Janusz A. Brzozowski and Rina S. Cohen. Dot-Depth of Star-Free Events. J. Comp. Sys. Sci., 5(1):1-16, 1971. Google Scholar
  5. Manuel Delgado. Abelian pointlikes of a monoid. Semigroup Forum, 56:339-361, 1998. Google Scholar
  6. Volker Diekert and Tobias Walter. Characterizing classes of regular languages using prefix codes of bounded synchronization delay. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP'16, pages 129:1-129:14, 2016. Google Scholar
  7. Volker Diekert and Tobias Walter. Characterizing classes of regular languages using prefix codes of bounded synchronization delay. IJAC, 27(6):561-590, 2017. Google Scholar
  8. Samuel Eilenberg. Automata, languages, and machines, volume B. Academic Press, 1976. Google Scholar
  9. Karsten Henckell. Pointlike sets: the finest aperiodic cover of a finite semigroup. Journal of Pure Applied Algebra, 55(1-2):85-126, 1988. Google Scholar
  10. Joel Karnofsky and John Rhodes. Decidability of complexity one-half for finite semigroups. Semigroup Forum, 24(1):55-66, 1982. URL: http://dx.doi.org/10.1007/BF02572755.
  11. Stuart W. Margolis and Jean-Éric Pin. Products of group languages. In FCT'85. Springer, 1985. Google Scholar
  12. Robert McNaughton and Seymour A. Papert. Counter-Free Automata. MIT Press, 1971. Google Scholar
  13. Jean-Éric Pin. Bridges for Concatenation Hierarchies. In ICALP'98, pages 431-442. Springer, 1998. Google Scholar
  14. Jean-Éric Pin. The dot-depth hierarchy, 45 years later. In The Role of Theory in Computer Science. Essays Dedicated to Janusz Brzozowski. World Scientific Publishing, 2017. Google Scholar
  15. Jean-Éric Pin. Mathematical Foundations of Automata Theory. Lecture notes, 2019. URL: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf.
  16. Jean-Éric Pin, Howard Straubing, and Denis Thérien. Locally trivial categories and unambiguous concatenation. Journal of Pure and Applied Algebra, 52(3):297-311, 1988. Google Scholar
  17. Thomas Place. Separating Regular Languages with Two Quantifiers Alternations. In LICS'15, pages 202-213. IEEE Computer Society, 2015. Google Scholar
  18. Thomas Place. Separating regular languages with two quantifier alternations. Logical Methods in Computer Science, 14(4), 2018. Google Scholar
  19. Thomas Place and Marc Zeitoun. Going Higher in the First-Order Quantifier Alternation Hierarchy on Words. In ICALP'14, pages 342-353, 2014. Google Scholar
  20. Thomas Place and Marc Zeitoun. Separating Regular Languages with First-Order Logic. Logical Methods in Computer Science, 12(1), 2016. Google Scholar
  21. Thomas Place and Marc Zeitoun. Separation for Dot-Depth Two. In 32th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'17, 2017. URL: http://arxiv.org/abs/1901.03361.
  22. Thomas Place and Marc Zeitoun. Generic results for concatenation hierarchies. Theory of Computing Systems (ToCS), 2018. Selected papers from CSR'17. Google Scholar
  23. Thomas Place and Marc Zeitoun. Separation for dot-depth two. In preparation, preprint at http://www.labri.fr/~zeitoun/research/pdf/boolpol-full.pdf, 2018.
  24. Thomas Place and Marc Zeitoun. The Covering Problem. Logical Methods in Computer Science, 14(3), 2018. Google Scholar
  25. Thomas Place and Marc Zeitoun. On all things star-free. Full version of this paper, https://arxiv.org/abs/1904.11863, 2019.
  26. Thomas Place and Marc Zeitoun. Separation and covering for group based concatenation hierarchies. In LICS'19, 2019. Google Scholar
  27. Marcel Paul Schützenberger. On Finite Monoids Having Only Trivial Subgroups. Information and Control, 8(2):190-194, 1965. Google Scholar
  28. Marcel Paul Schützenberger. Sur certaines opérations de fermeture dans les langages rationnels. Symposia Mathematica, XV:245-253, 1975. Convegno di Informatica Teorica, INDAM, Roma, 1973. Google Scholar
  29. Howard Straubing. Aperiodic homomorphisms and the concatenation product of recognizable sets. Journal of Pure and Applied Algebra, 15(3):319-327, 1979. Google Scholar
  30. Wolfgang Thomas. Classifying Regular Events in Symbolic Logic. J. Comp. Sys. Sci., 25(3):360-376, 1982. Google Scholar
  31. Thomas Wilke. Classifying Discrete Temporal Properties. In Proceedings of the 16th Annual Conference on Theoretical Aspects of Computer Science, STACS'99, pages 32-46, 1999. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact