Definability equals recognizability of partial 3-trees and \(k\)-connected partial \(k\)-trees

DOI10.1007/s004530010024zbMath0959.68095OpenAlexW1976364198MaRDI QIDQ1578419

D. Kaller

Publication date: 27 August 2000

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004530010024

zbMATH Keywords

tree automatongraph decision problems

Mathematics Subject Classification ID

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

Related Items

Fixed-Parameter Tractability of Treewidth and Pathwidth, Recognizability equals definability for graphs of bounded treewidth and bounded chordality, Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees, Recognizability equals definability for partial k-paths, The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs, Causality in Bounded Petri Nets is MSO Definable