Simple monadic theories and partition width

DOI10.1002/malq.201010019zbMath1247.03063MaRDI QIDQ3170562

Achim Blumensath

Publication date: 27 September 2011

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.201010019

zbMATH Keywords

monadic second-order logic; indiscernible sequences; partition width; definable pairing functions; tree-like decompositions of models

Mathematics Subject Classification ID

03C45: Classification theory, stability, and related concepts in model theory

03C50: Models with special properties (saturated, rigid, etc.)

03C85: Second- and higher-order model theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• Axiomatising tree-interpretable structures
• Graph minors. III. Planar tree-width
• The monadic second-order logic of graphs. IV: Definability properties of equational graphs
• The structure of the models of decidable monadic theories of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• On the structure of graphs in the Caucal hierarchy
• Monadic logic and Löwenheim numbers
• Second-order quantifiers and the complexity of theories
• Around classification theory of models
• Classification theory and the number of non-isomorphic models.
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• S-functions for graphs
• The monadic theory of order
• Clique-width of countable graphs: A compactness property.
• Monadic second-order logic on tree-like structures
• Structural properties of context-free sets of graphs generated by vertex replacement
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Recognizability, hypergraph operations, and logical types
• A model-theoretic characterisation of clique width
• The recognizability of sets of graphs is a robust property
• Simple monadic theories and indiscernibles
• Fusion in relational structures and the verification of monadic second-order properties
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Modest theory of short chains. I
• Modest theory of short chains. II
• The Monadic Theory of Tree-like Structures
• An Extension of Muchnik's Theorem
• Model Theory
• Transforming structures by set interpretations
• Decidability of Second-Order Theories and Automata on Infinite Trees