Recognizability equals definability for partial k-paths

DOI10.1007/3-540-63165-8_233zbMath1401.03066OpenAlexW1804454173MaRDI QIDQ4572008

Valentine Kabanets

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_233

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Towards a language theory for infinite N-free pomsets. ⋮ 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 ⋮ Minor obstructions for apex-pseudoforests ⋮ Causality in Bounded Petri Nets is MSO Definable

Cites Work

• The structure of the models of decidable monadic theories of graphs
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Definability equals recognizability of partial 3-trees and \(k\)-connected partial \(k\)-trees
• The monadic second-order logic of graphs. VIII: Orientations
• Tree acceptors and some of their applications
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Weak Second‐Order Arithmetic and Finite Automata
• Graph minors. II. Algorithmic aspects of tree-width
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Recognizability equals definability for partial k-paths