Definability equals recognizability for k-outerplanar graphs

DOI10.4230/LIPICS.IPEC.2015.175zbMATH Open1378.03032arXiv1509.08315OpenAlexW2223243427MaRDI QIDQ5363771FDOQ5363771

Authors: Lars Jaffke, Hans L. Bodlaender 

Publication date: 29 September 2017

Abstract: One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in linear time for graphs of bounded treewidth, which is known as Courcelle's Theorem. These algorithms are constructed as finite state tree automata, and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. We prove this conjecture for $k$-outerplanar graphs, which are known to have treewidth at most $3k-1$.

Full work available at URL: https://arxiv.org/abs/1509.08315

Recommendations

• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Definability equals recognizability for graphs of bounded treewidth
• Definability equals recognizability of partial 3-trees and \(k\)-connected partial \(k\)-trees
• scientific article; zbMATH DE number 1136093
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability

zbMATH Keywords

treewidth\(k\)-outerplanar graphsmonadic second-order logic of graphsfinite-state tree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)

Cited In (8)

• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• Recognizability equals definability for partial k-paths
• Definability equals recognizability for graphs of bounded treewidth
• Causality in bounded Petri nets is MSO definable
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Definability equals recognizability of partial 3-trees
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Title not available (Why is that?)

This page was built for publication: Definability equals recognizability for \(k\)-outerplanar graphs

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