Separating Regular Languages over Infinite Words with Respect to the Wagner Hierarchy

Author Christopher Hugenroth



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.46.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Christopher Hugenroth
  • TU Ilmenau, Germany

Acknowledgements

I want to thank Christof Löding who supervised my Master thesis on which this paper is based and Dietrich Kuske for clarifying discussions. Further, I want to thank the reviewers of former versions of this paper for their helpful suggestions.

Cite AsGet BibTex

Christopher Hugenroth. Separating Regular Languages over Infinite Words with Respect to the Wagner Hierarchy. 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. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.46

Abstract

We investigate the separation problem for regular ω-languages with respect to the Wagner hierarchy where the input languages are given as deterministic Muller automata (DMA). We show that a minimal separating DMA can be computed in exponential time and that some languages require separators of exponential size. Further, we show that in this setting it can be decided in polynomial time whether a separator exists on a certain level of the Wagner hierarchy and that emptiness of the intersection of two languages given by DMAs can be decided in polynomial time. Finally, we show that separation can also be decided in polynomial time if the input languages are given as deterministic parity automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
  • Theory of computation → Regular languages
Keywords
  • Separation
  • Regular
  • Wagner Hierarchy
  • Muller Automata
  • Parity Automata
  • Product Automata
  • Membership

Metrics

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

References

  1. Udi Boker. On the (in) succinctness of Muller automata. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  2. Udi Boker. Why these automata types? In LPAR, volume 18, pages 143-163, 2018. Google Scholar
  3. Olivier Carton and Ramón Maceiras. Computing the Rabin index of a parity automaton. RAIRO-Theoretical Informatics and Applications, 33(6):495-505, 1999. Google Scholar
  4. Thomas Colcombet and Christof Löding. The nesting-depth of disjunctive μ-calculus for tree languages and the limitedness problem. In International Workshop on Computer Science Logic, pages 416-430. Springer, 2008. Google Scholar
  5. Damian Niwiński and Igor Walukiewicz. Relating hierarchies of word and tree automata. In Annual Symposium on Theoretical Aspects of Computer Science, pages 320-331. Springer, 1998. Google Scholar
  6. Damian Niwiński and Igor Walukiewicz. Deciding nondeterministic hierarchy of deterministic tree automata. Electronic Notes in Theoretical Computer Science, 123:195-208, 2005. Google Scholar
  7. Dominique Perrin and Jean-Éric Pin. Infinite words: automata, semigroups, logic and games. Academic Press, 2004. Google Scholar
  8. Thomas Place and Marc Zeitoun. Separating regular languages with first-order logic. In Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-10, 2014. Google Scholar
  9. Thomas Place and Marc Zeitoun. The tale of the quantifier alternation hierarchy of first-order logic over words. ACM SIGLOG News, 2(3):4-17, 2015. Google Scholar
  10. Shmuel Safra. Complexity of automata on infinite objects. PhD thesis, The Weizmann Institute of Science, 1989. Google Scholar
  11. Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Inf. Control., 8(2):190-194, 1965. Google Scholar
  12. Klaus Wagner. On ω-regular sets. Information and control, 43(2):123-177, 1979. 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