Recognizable sets of graphs of bounded tree-width

DOI10.1007/3-540-57787-4_9MaRDI QIDQ5096279zbMATH OpenOpenAlexFDO

Authors Jens Lagergren, Bruno Courcelle

Publication date 16 August 2022

Published in Graph Transformations in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57787-4_9

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Recommendations

• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• scientific article; zbMATH DE number 1136093
• Recognizable sets of graphs: equivalent definitions and closure properties
• The recognizability of sets of graphs is a robust property
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cites work

• scientific article; zbMATH DE number 4160146 (Why is no real title available?)
• scientific article; zbMATH DE number 177426 (Why is no real title available?)
• scientific article; zbMATH DE number 475614 (Why is no real title available?)
• Easy problems for tree-decomposable graphs
• Recognizable sets of graphs: equivalent definitions and closure properties
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• 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

Cited in

(5)

• scientific article; zbMATH DE number 841653 (Why is no real title available?)
• Definability equals recognizability for graphs of bounded treewidth
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• The recognizability of sets of graphs is a robust property
• Recognizable sets of graphs: equivalent definitions and closure properties

This page was built for publication: Recognizable sets of graphs of bounded tree-width

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