Equivalent definitions of recognizability for sets of graphs of bounded tree-width

DOI10.1017/S096012950000092XMaRDI QIDQ4882496zbMATH OpenFDO

Authors Jens Lagergren, Bruno Courcelle

Publication date 12 September 1996

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S096012950000092X

zbMATH Keywords

finite graphstree-width

Mathematics Subject Classification ID

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

Recommendations

• Recognizable sets of graphs of bounded tree-width
• scientific article; zbMATH DE number 1136093
• Recognizable sets of graphs: equivalent definitions and closure properties
• Definability equals recognizability for graphs of bounded treewidth
• The recognizability of sets of graphs is a robust property

Cites work

• Algebraic automata and context-free sets
• An algebraic theory of graph reduction
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(16)

• On computing graph minor obstruction sets
• Recognizability, hypergraph operations, and logical types
• The recognizability of sets of graphs is a robust property
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Bicycles and Spanning Trees
• Recognizable sets of graphs: equivalent definitions and closure properties
• scientific article; zbMATH DE number 1136093 (Why is no real title available?)
• Recognizability equals definability for partial k-paths
• Definability equals recognizability for graphs of bounded treewidth
• Optimizing tree decompositions in MSO
• Computing Tree Decompositions
• A linear fixed parameter tractable algorithm for connected pathwidth
• Recognizable sets of graphs of bounded tree-width
• scientific article; zbMATH DE number 7204410 (Why is no real title available?)
• scientific article; zbMATH DE number 7651203 (Why is no real title available?)
• Characterizations of monadic second order definable context-free sets of graphs

This page was built for publication: Equivalent definitions of recognizability for 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 Q4882496)