Regular expressions for languages of graphs of tree-width 2

Speaker(s)

Amina Doumane

Affiliation

CNRS-ENS Lyon

Date

June 9, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

I propose a syntax of regular expressions which capture exactly CMSO definable languages of graphs of tree-width 2. A similar syntax is given for CMSO definable languages of series-parallel graphs and of connected tree-width 2 graphs.

---