Graph decompositions definable in monadic second-order logic

DOI10.1016/J.ENDM.2005.06.003MaRDI QIDQ3439302zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2005.06.003

zbMATH Keywords

graph decompositionmatroidmonadic second-order logicsplit decomposition

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Graph equivalences and decompositions definable in monadic second-order logic. The case of circle graphs
• The definition in monadic second-order logic of modular decompositions of ordered graphs
• Computer Science Logic
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic

Cites work

• A k-structure generalization of the theory of 2-structures
• A Combinatorial Decomposition Theory
• A linear algorithm to decompose inheritance graphs into modules
• Computer Science Logic
• Decomposition of Directed Graphs
• Handbook of Graph Grammars and Computing by Graph Transformation
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 1107727 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• Partitive hypergraphs
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
• Theory of Matroids

Cited in

(13)

• A regular characterization of graph languages definable in monadic second-order logic
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
• Graph equivalences and decompositions definable in monadic second-order logic. The case of circle graphs
• scientific article; zbMATH DE number 4124985 (Why is no real title available?)
• Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic
• Prefix-Recognizable Graphs and Monadic Logic
• The definition in monadic second-order logic of modular decompositions of ordered graphs
• Context-Free Graph Properties via Definable Decompositions
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Computer Science Logic
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Circle graphs and monadic second-order logic

This page was built for publication: Graph decompositions definable in monadic second-order logic

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