Simple monadic theories and partition width

Mathematical Logic Quarterly 57 (4):409-431 (2011)

Abstract
We study tree-like decompositions of models of a theory and a related complexity measure called partition width. We prove a dichotomy concerning partition width and definable pairing functions: either the partition width of models is bounded, or the theory admits definable pairing functions. Our proof rests on structure results concerning indiscernible sequences and finitely satisfiable types for theories without definable pairing functions. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
Keywords Monadic second‐order logic  partition width  MSC (2010) 03C45  model theory  03C85  03C50
Categories (categorize this paper)
DOI 10.1002/malq.201010019
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,683
Through your library

References found in this work BETA

Modest Theory of Short Chains. I.Yuri Gurevich - 1979 - Journal of Symbolic Logic 44 (4):481-490.
Second-Order Quantifiers and the Complexity of Theories.J. T. Baldwin & S. Shelah - 1985 - Notre Dame Journal of Formal Logic 26 (3):229-303.
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 Structure of the Models of Decidable Monadic Theories of Graphs.D. Seese - 1991 - Annals of Pure and Applied Logic 53 (2):169-195.

View all 9 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Analytics

Added to PP index
2013-11-03

Total views
21 ( #390,915 of 2,242,907 )

Recent downloads (6 months)
11 ( #104,878 of 2,242,907 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature