The structure of the models of decidable monadic theories of graphs

Annals of Pure and Applied Logic 53 (2):169-195 (1991)
  Copy   BIBTEX

Abstract

In this article the structure of the models of decidable monadic theories of planar graphs is investigated. It is shown that if the monadic theory of a class K of planar graphs is decidable, then the tree-width in the sense of Robertson and Seymour of the elements of K is universally bounded and there is a class T of trees such that the monadic theory of K is interpretable in the monadic theory of T

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(91)90054-p

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,247

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The monadic second-order logic of graphs VIII: Orientations.Bruno Courcelle - 1995 - Annals of Pure and Applied Logic 72 (2):103-143.
Logical aspects of Cayley-graphs: the group case.Dietrich Kuske & Markus Lohrey - 2004 - Annals of Pure and Applied Logic 131 (1-3):263-286.
On countable chains having decidable monadic theory.Alexis Bés & Alexander Rabinovich - 2012 - Journal of Symbolic Logic 77 (2):593-608.
Random graphs in the monadic theory of order.Shmuel Lifsches & Saharon Shelah - 1999 - Archive for Mathematical Logic 38 (4-5):273-312.
The monadic second-order logic of graphs XV: On a conjecture by D. Seese.Bruno Courcelle - 2006 - Journal of Applied Logic 4 (1):79-114.
Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second‐Order Logic.Iain A. Stewart - 1997 - Mathematical Logic Quarterly 43 (1):1-21.
The monadic second-order logic of graphs IV: Definability properties of equational graphs.Bruno Courcelle - 1990 - Annals of Pure and Applied Logic 49 (3):193.
Monadic second-order properties of very sparse random graphs.L. B. Ostrovsky & M. E. Zhukovskii - 2017 - Annals of Pure and Applied Logic 168 (11):2087-2101.
Existential monadic second order logic of undirected graphs: The Le Bars conjecture is false.S. N. Popova & M. E. Zhukovskii - 2019 - Annals of Pure and Applied Logic 170 (4):505-514.
Monadic Bounded Algebras.Galym Akishev & Robert Goldblatt - 2010 - Studia Logica 96 (1):1 - 40.

Analytics

Added to PP
2014-01-16

Downloads
32 (#705,389)

6 months
12 (#294,748)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Algorithmic uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
A model-theoretic characterisation of clique width.Achim Blumensath - 2006 - Annals of Pure and Applied Logic 142 (1):321-350.
The monadic second-order logic of graphs VIII: Orientations.Bruno Courcelle - 1995 - Annals of Pure and Applied Logic 72 (2):103-143.
Simple monadic theories and partition width.Achim Blumensath - 2011 - Mathematical Logic Quarterly 57 (4):409-431.
Logical aspects of Cayley-graphs: the group case.Dietrich Kuske & Markus Lohrey - 2004 - Annals of Pure and Applied Logic 131 (1-3):263-286.

View all 7 citations / Add more citations

References found in this work

Mathematical logic.Heinz-Dieter Ebbinghaus - 1996 - New York: Springer. Edited by Jörg Flum & Wolfgang Thomas.
Monadic theory of order and topology in ZFC.Yuri Gurevich & Saharon Shelah - 1982 - Annals of Mathematical Logic 23 (2-3):179-198.
Modest theory of short chains. I.Yuri Gurevich - 1979 - Journal of Symbolic Logic 44 (4):481-490.
The monadic theory of ω2.Yuri Gurevich, Menachem Magidor & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (2):387-398.

View all 14 references / Add more references