The modular decomposition of countable graphs. Definition and construction in monadic second-order logic

DOI10.1016/j.tcs.2007.10.046zbMath1136.68041OpenAlexW2020917861MaRDI QIDQ2481975

Bruno Courcelle, Christian Delhommé

Publication date: 15 April 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.10.046

zbMATH Keywords

treemonadic second-order logicmodular decompositionlinear ordermonadic second-order transduction

Mathematics Subject Classification ID

Related Items (13)

Induced betweenness in order-theoretic trees ⋮ Order-theoretic Trees: Monadic Second-order Descriptions and Regularity ⋮ An Analytic Propositional Proof System on Graphs ⋮ Unnamed Item ⋮ Decomposition of tournament limits ⋮ Unnamed Item ⋮ Regularity Equals Monadic Second-Order Definability for Quasi-trees ⋮ Nash equilibria and values through modular partitions in infinite games ⋮ Prechains and self duality ⋮ \((\leq k)\)-reconstructible binary relations ⋮ Unnamed Item ⋮ Several notions of rank-width for countable graphs ⋮ A type of algebraic structure related to sets of intervals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• On the regular structure of prefix rewriting
• The monadic second-order logic of graphs. IV: Definability properties of equational graphs
• Primitivity is hereditary for 2-structures
• Fundamental properties of infinite trees
• On better quasi-ordering countable trees
• Theory of relations. Transl. from the French by P. Clote
• The theory of ends, pushdown automata, and second-order logic
• Langages algébriques de mots biinfinis. (Algebraic languages of biinfinite words)
• Monadic second-order definable graph transductions: a survey
• The monadic second-order logic of graphs. X: Linear orderings
• Indecomposable graphs
• Clique-width of countable graphs: A compactness property.
• The evaluation of first-order substitution is monadic second-order compatible
• Finite presentations of infinite structures: Automata and interpretations
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Decomposition of Directed Graphs
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• The monadic second-order logic of graphs XVI : Canonical graph decompositions
• Computer Science Logic
• Computer Science Logic
• Transitiv orientierbare Graphen
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: The modular decomposition of countable graphs. Definition and construction in monadic second-order logic