Characterizations of monadic second order definable context-free sets of graphs

DOI10.46298/LMCS-22(1:22)2026MaRDI QIDQ6840489zbMATH OpenFDO

Authors Radu Iosif, Florian Zuleger

Publication date 23 March 2026

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/LMCS-22(1:22)2026

zbMATH Keywords

graph grammarsmonadic second order logicrecognizabilitytree-width

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• A note on undecidable properties of formal languages
• A partial k-arboretum of graphs with bounded treewidth
• Algebraic automata and context-free sets
• Definability equals recognizability for graphs of bounded treewidth
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• Expressiveness results for an inductive logic of separated relations
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• Optimizing tree decompositions in MSO
• Regular expressions for tree-width 2 graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Tree acceptors and some of their applications
• Tree-verifiable graph grammars

This page was built for publication: Characterizations of monadic second order definable context-free sets of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6840489)