The structure of the models of decidable monadic theories of graphs
type: Item
instance of: scholarly article
title: The structure of the models of decidable monadic theories of graphs
zbMATH Open document ID: 0733.03026
DOI: 10.1016/0168-0072(91)90054-P
published in: Annals of Pure and Applied Logic
publication date: 1991-01-01T00:00:00Z
review text: The author devotes the bulk of this paper to a proof of the following undecidability result. If K is a class of graphs such that for each planar graph H there is a planar graph \(G\in K\) with H isomorphic to a minor of G, then both the second-order monadic and weak second-order monadic theories of K are undecidable. This generalizes an earlier theorem of the author. The author then quickly deduces that if the (weak) monadic theory of a class K of planar graphs is decidable then the tree-width of the graphs in K is universally bounded and there is a class T of trees such that the (weak) monadic theory of K is interpretable in the (weak) monadic theory of T. The paper ends with three open problems.
Mathematics Subject Classification ID: 03C65
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 4212021
zbMATH Keywords: undecidability
zbMATH Keywords: planar graph
zbMATH Keywords: second-order monadic theories
zbMATH Keywords: tree-width
author: Detlef Seese
reviewed by: J. M. Plotkin
MaRDI profile type: Publication
cites work: Q3812222
cites work: Q3884080
cites work: The undecidability of the domino problem
cites work: Q3852212
cites work: Q3677732
cites work: Q4143272
cites work: The monadic second order theory of all countable ordinals
cites work: Q3220545
cites work: Q3773882
cites work: The Undecidability of Theories of Groupoids with an Extra Predicate
cites work: Monadic theory of order and topology, I
cites work: Modest theory of short chains. I
cites work: Monadic theory of order and topology. II
cites work: The monadic theory of ω2
cites work: Modest theory of short chains. II
cites work: Monadic theory of order and topology in ZFC
cites work: Interpreting second-order logic in the monadic theory of order
cites work: Ein Zerlegungssatz für unendliche Graphen und seine Anwendung auf Homomorphiebasen
cites work: Parallel concepts in graph theory
cites work: The NP-completeness column: An ongoing guide
cites work: Model-interpretability into trees and applications
cites work: Set theory. With an introduction to descriptive set theory. Translation of the original Polish edition. 2nd, completely revised ed
cites work: Q5586299
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: Graph minors. I. Excluding a forest
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Graph minors. III. Planar tree-width
cites work: Q3684139
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. VI. Disjoint paths across a disc
cites work: Disjoint Paths—A Survey
cites work: Q3680875
cites work: Q4734768
cites work: A combinatorial and logical approach to linear-time computability (extended abstract)
cites work: Decidability and ℵ0-categoricity of theories of partially ordered sets
cites work: Decidability and finite axiomatizability of theories of ℵ0-categorical partially ordered sets
cites work: Arborescent Structures. II: Interpretability in the Theory of Trees
cites work: Q4097268
cites work: Q4135492
cites work: Q5668796
cites work: Some Graph Theoretical Operations and Decidability
cites work: Q3692864
cites work: Über Unentscheidbare Erweiterungen von SC
cites work: Grids and their minors
cites work: The monadic theory of order
cites work: Q5537599
cites work: Büchi's monadic second order successor arithmetic.
cites work: Q3041212
cites work: Q3216652
full work available at URL: 0168-0072(91)90054-p
OpenAlex ID: W2029001691
description: scientific article; zbMATH DE number 4212021