A model-theoretic characterisation of clique width

Annals of Pure and Applied Logic 142 (1):321-350 (2006)
  Copy   BIBTEX

Abstract

We generalise the concept of clique width to structures of arbitrary signature and cardinality. We present characterisations of clique width in terms of decompositions of a structure and via interpretations in trees. Several model-theoretic properties of clique width are investigated including VC-dimension and preservation of finite clique width under elementary extensions and compactness

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2006.02.004

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,283

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

Simple monadic theories and partition width.Achim Blumensath - 2011 - Mathematical Logic Quarterly 57 (4):409-431.
On spectra of sentences of monadic second order logic with counting.E. Fischer & J. A. Makowsky - 2004 - Journal of Symbolic Logic 69 (3):617-640.
The Philosophical Significance of Tennenbaum’s Theorem.T. Button & P. Smith - 2012 - Philosophia Mathematica 20 (1):114-121.
Correction to `a model theoretic characterisation of effective operations'.M. H. Löb - 1974 - Journal of Symbolic Logic 39 (2):225.
Saturated models of universal theories.Jeremy Avigad - 2002 - Annals of Pure and Applied Logic 118 (3):219-234.
Models and modality.Patricia A. Blanchette - 2000 - Synthese 124 (1-2):45-72.
Finite conformal hypergraph covers and Gaifman cliques in finite structures.Ian Hodkinson & Martin Otto - 2003 - Bulletin of Symbolic Logic 9 (3):387-405.
The model-theoretic ordinal analysis of theories of predicative strength.Jeremy Avigad & Richard Sommer - 1999 - Journal of Symbolic Logic 64 (1):327-349.
Is human conversation more efficient than chimpanzee grooming?Michio Nakamura - 2000 - Human Nature 11 (3):281-297.
Thermal gradients as control factors for leaf size variations at different altitudes in mountains.A. N. Purohit & P. P. Dhyani - 1988 - Acta Biotheoretica 37 (1):3-26.
The structure of logical consequence : proof-theoretic conceptions.Ole T. Hjortland - unknown
Ramseyfication and theoretical content.Joseph Melia & Juha Saatsi - 2006 - British Journal for the Philosophy of Science 57 (3):561-585.
Schlanke Körper (Slim fields).Markus Junker & Jochen Koenigsmann - 2010 - Journal of Symbolic Logic 75 (2):481-500.
What is the model-theoretic argument?David Leech Anderson - 1993 - Journal of Philosophy 90 (6):311-322.
The Concept of Logical Consequence: An Introduction to Philosophical Logic.Matthew W. McKeon - 2010 - Peter Lang.

Analytics

Added to PP
2013-12-31

Downloads
17 (#873,341)

6 months
7 (#439,668)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Locality and modular Ehrenfeucht–Fraïssé games.Achim Blumensath - 2012 - Journal of Applied Logic 10 (1):144-162.
Simple monadic theories and partition width.Achim Blumensath - 2011 - Mathematical Logic Quarterly 57 (4):409-431.
Simple monadic theories and indiscernibles.Achim Blumensath - 2011 - Mathematical Logic Quarterly 57 (1):65-86.

Add more citations

References found in this work

Second-order quantifiers and the complexity of theories.J. T. Baldwin & S. Shelah - 1985 - Notre Dame Journal of Formal Logic 26 (3):229-303.
The structure of the models of decidable monadic theories of graphs.D. Seese - 1991 - Annals of Pure and Applied Logic 53 (2):169-195.
Undecidability of the Domino Problem.Robert Berger - 1966 - American Mathematical Soc..
Théories d'arbres.Michel Parigot - 1982 - Journal of Symbolic Logic 47 (4):841-853.

Add more references