Recognizability equals definability for partial k-paths

DOI10.1007/3-540-63165-8_233MaRDI QIDQ4572008zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Definability equals recognizability of partial 3-trees and k-connected partial k-trees
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Definability equals recognizability for k-outerplanar graphs
• Definability equals recognizability for graphs of bounded treewidth
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• scientific article; zbMATH DE number 1136093
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• On Several Proofs of the Recognizability Theorem
• scientific article; zbMATH DE number 5000345
• Definability in the Recursively Enumerable Degrees

Cites work

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

Cited in

(12)

• Definability equals recognizability of partial 3-trees and k-connected partial k-trees
• Towards a language theory for infinite N-free pomsets.
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
• Minor obstructions for apex-pseudoforests
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Causality in bounded Petri nets is MSO definable
• Fixed-parameter tractability of treewidth and pathwidth
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• scientific article; zbMATH DE number 1104369 (Why is no real title available?)
• Recognizability equals definability for partial k-paths
• Definability equals recognizability for graphs of bounded treewidth
• Definability equals recognizability of partial 3-trees

This page was built for publication: Recognizability equals definability for partial k-paths

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