On September 15, 2025 at 15:00 EEST, Radu Iosif (CNRS-VERIMAG) will give a talk in the Logic Seminar.
VERY IMPORTANT! The talk will take place physically at the PBTower building (the new location of FMI-UNIBUC), Hall 415.
Title: Regular Grammars for Sets of Graphs of Tree-Width 2
Abstract:
Regular word grammars are restricted context-free grammars that define all the recognizable languages of words. This paper generalizes regular grammars from words to certain classes of graphs, by defining regular grammars for unordered unranked trees and graphs of tree-width 2 at most. The qualifier “regular” is justified because these grammars define precisely the recognizable (equivalently, CMSO-definable) sets of the respective graph classes. The proof of equivalence between regular and recognizable sets of graphs relies on the effective construction of a recognizer algebra of size doubly-exponential in the size of the grammar. This sets a 2EXPTIME upper bound on the (EXPTIME-hard) problem of inclusion of a context-free language in a regular language, for graphs of tree-width 2 at most. A further syntactic restriction of regular grammars suffices to capture precisely the MSO-definable sets of graphs of tree-width 2 at most, i.e., the sets defined by CMSO formulae without cardinality constraints. Moreover, we show that MSO-definability coincides with recognizability by algebras having an aperiodic parallel composition semigroup, for each class of graphs defined by a bound on the tree-width. Joint work with Marius Bozga (VERIMAG) and Florian Zuleger (TU Wien) presented at LICS 2025.