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

DOI10.1017/S096012950000092XzbMATH Open0846.68054MaRDI QIDQ4882496FDOQ4882496

Authors: Jens Lagergren, Bruno Courcelle 

Publication date: 12 September 1996

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

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

zbMATH Keywords

finite graphstree-width

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• Recognizability, hypergraph operations, and logical types
• On computing graph minor obstruction sets
• Recognizability equals definability for partial k-paths
• Definability equals recognizability for graphs of bounded treewidth
• Computing Tree Decompositions
• Myhill-Nerode Methods for Hypergraphs
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Title not available (Why is that?)
• Title not available (Why is that?)
• The recognizability of sets of graphs is a robust property
• Recognizable sets of graphs: equivalent definitions and closure properties
• Bicycles and Spanning Trees
• Title not available (Why is that?)
• A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth

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)