Regular Expressions for Tree-Width 2 Graphs
Amina Doumane · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2022
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).