Regularity equals monadic second-order definability for quasi-trees

DOI10.1007/978-3-319-23534-9_7MaRDI QIDQ2947169zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 22 September 2015

Published in Fields of Logic and Computation II (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-23534-9_7

Mathematics Subject Classification ID

Model theory of denumerable and separable structures (03C15) Models of other mathematical theories (03C65) Second- and higher-order model theory (03C85)

Recommendations

• Algebraic and logical descriptions of generalized trees
• STACS 2005
• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• scientific article; zbMATH DE number 1136093

Cites work

• Approximating clique-width and branch-width
• Clique-sums, tree-decompositions and compactness
• Clique-width of countable graphs: A compactness property.
• Fundamental properties of infinite trees
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• scientific article; zbMATH DE number 3675332 (Why is no real title available?)
• scientific article; zbMATH DE number 3639170 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• Logical theories and compatible operations
• On frontiers of regular trees
• Rank-width and vertex-minors
• Regularity equals monadic second-order definability for quasi-trees
• Several notions of rank-width for countable graphs
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic

Cited in

(6)

• Regularity equals monadic second-order definability for quasi-trees
• Order-theoretic Trees: Monadic Second-order Descriptions and Regularity
• Betweenness in order-theoretic trees
• Algebraic and logical descriptions of generalized trees
• Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law
• Axiomatization of betweenness in order-theoretic trees

This page was built for publication: Regularity equals monadic second-order definability for quasi-trees

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