The structure of the models of decidable monadic theories of graphs

DOI10.1016/0168-0072(91)90054-PzbMath0733.03026OpenAlexW2029001691MaRDI QIDQ810005

Detlef Seese

Publication date: 1991

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(91)90054-p

zbMATH Keywords

undecidabilityplanar graphtree-widthsecond-order monadic theories

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Decidability of theories and sets of sentences (03B25) Graph theory (05C99) Models of other mathematical theories (03C65)

Related Items

Trees, grids, and MSO decidability: from graphs to matroids, The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., Compactors for parameterized counting problems, The monadic second order logic of graphs. VI: On several representations of graphs by relational structures, Simple monadic theories and partition width, Tree automata and pigeonhole classes of matroids. I, Vertex-minors, monadic second-order logic, and a conjecture by Seese, The monadic second-order logic of graphs, II: Infinite graphs of bounded width, Algorithmic uses of the Feferman-Vaught theorem, Recognizability equals definability for partial k-paths, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, Subshifts as models for MSO logic, A monadic second-order definition of the structure of convex hypergraphs., Tree-width and the monadic quantifier hierarchy., Monadic second-order logic and the domino problem on self-similar graphs, Clique-width of countable graphs: A compactness property., 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07, The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability, Upper bounds to the clique width of graphs, Excluded Forest Minors and the Erdős–Pósa Property, Properties of graphs specified by a regular language, Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete, On the path-width of integer linear programming, Rabin's theorem in the concurrency setting: a conjecture, Properties of graphs specified by a regular language, Graph Operations, Graph Transformations and Monadic Second-Order Logic:, Logical aspects of Cayley-graphs: the group case, Branch-width, parse trees, and monadic second-order logic for matroids., Grid structures and undecidable constraint theories, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, A model-theoretic characterisation of clique width, Computing with Tangles, Treewidth and logical definability of graph products, Simple monadic theories and indiscernibles, On the width of regular classes of finite structures, Subshifts, Languages and Logic, Nondeterministic operations on finite relational structures, The monadic second-order logic of graphs. VIII: Orientations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Graph minors. I. Excluding a forest
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. V. Excluding a planar graph
• Grids and their minors
• Monadic theory of order and topology. II
• The monadic second order theory of all countable ordinals
• Set theory. With an introduction to descriptive set theory. Translation of the original Polish edition. 2nd, completely revised ed
• The monadic theory of order
• Monadic theory of order and topology, I
• Büchi's monadic second order successor arithmetic.
• Parallel concepts in graph theory
• Some Graph Theoretical Operations and Decidability
• The monadic theory of ω₂
• Interpreting second-order logic in the monadic theory of order
• Monadic theory of order and topology in ZFC
• Disjoint Paths—A Survey
• Graph minors. II. Algorithmic aspects of tree-width
• Decidability and ℵ₀-categoricity of theories of partially ordered sets
• Modest theory of short chains. I
• Modest theory of short chains. II
• Decidability and finite axiomatizability of theories of ℵ₀-categorical partially ordered sets
• Arborescent Structures. II: Interpretability in the Theory of Trees
• Model-interpretability into trees and applications
• Über Unentscheidbare Erweiterungen von SC
• The Undecidability of Theories of Groupoids with an Extra Predicate
• A combinatorial and logical approach to linear-time computability (extended abstract)
• Ein Zerlegungssatz für unendliche Graphen und seine Anwendung auf Homomorphiebasen
• The undecidability of the domino problem
• Decidability of Second-Order Theories and Automata on Infinite Trees
• The NP-completeness column: An ongoing guide