Document Open Access Logo

Regular Expressions for Tree-Width 2 Graphs

Author Amina Doumane

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.121.pdf
  • Filesize: 0.81 MB
  • 20 pages

Document Identifiers

Author Details

Amina Doumane
  • CNRS, LIP, ENS Lyon, France

Acknowledgements

I want to thank Denis Kuperberg for helpful discussions on the content and presentation.

Cite AsGet BibTex

Amina Doumane. Regular Expressions for Tree-Width 2 Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 121:1-121:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.121

Abstract

We propose a syntax of regular expressions, which describes languages of tree-width 2 graphs. We show that these languages correspond exactly to those languages of tree-width 2 graphs, definable in the counting monadic second-order logic (CMSO).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • Tree width
  • MSO
  • Regular expressions

Metrics

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

References

  1. Mikolaj Bojanczyk and Michal Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In LICS, pages 407-416. ACM, 2016. Google Scholar
  2. Mikolaj Bojanczyk and Michal Pilipczuk. Optimizing tree decompositions in MSO. In STACS, volume 66 of LIPIcs, pages 15:1-15:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  3. J. Richard Büchi. Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1-6):66-92, 1960. URL: https://doi.org/0.1002/malq.19600060105.
  4. Enric Cosme-Llópez and Damien Pous. K4-free graphs as a free algebra. In MFCS, volume 83 of LIPIcs, pages 76:1-76:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  5. Bruno Courcelle and Joost Engelfriet. Graph structure and monadic second-order logic - A language-theoretic approach. In Encyclopedia of mathematics and its applications, 2012. Google Scholar
  6. Calvin C. Elgot. Decision problems of finite automata design and related arithmetics. Transactions of the American Mathematical Society, 98:21-51, 1961. Google Scholar
  7. Joost Engelfriet. A regular characterization of graph languages definable monadic second-order logic. Theor. Comput. Sci., 88(1):139-150, October 1991. URL: https://doi.org/10.1016/0304-3975(91)90078-G.
  8. Zsolt Gazdag and Zoltán L. Németh. A kleene theorem for bisemigroup and binoid languages. Int. J. Found. Comput. Sci., 22:427-446, 2011. Google Scholar
  9. Ferenc Gécseg and Magnus Steinby. Tree languages. In Handbook of Formal Languages, 1997. Google Scholar
  10. S.C. Kleene. Representation of events in nerve nets and finite automata. In C.E. Shannon and J. McCarthy, editors, Automata Studies, pages 3-40, 1956. Princeton. Google Scholar
  11. Dietrich Kuske and Ingmar Meinecke. Construction of tree automata from regular expressions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 45(3):347-370, 2011. URL: https://doi.org/10.1051/ita/2011107.
  12. Neil Robertson and Paul D. Seymour. Graph minors. IV. Tree-width and well-quasi-ordering. J. Comb. Theory, Ser. B, 48:227-254, 1990. Google Scholar
  13. James W. Thatcher and Jesse B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical systems theory, 2:57-81, 2005. 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 Imprint Privacy Contact