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: 93,098

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

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.
Finite conformal hypergraph covers and Gaifman cliques in finite structures.Ian Hodkinson & Martin Otto - 2003 - Bulletin of Symbolic Logic 9 (3):387-405.
Canonicity in Power and Modal Logics of Finite Achronal Width.Robert Goldblatt & Ian Hodkinson - forthcoming - Review of Symbolic Logic:1-31.
Simple monadic theories and partition width.Achim Blumensath - 2011 - Mathematical Logic Quarterly 57 (4):409-431.
Transitive Logics of Finite Width with Respect to Proper-Successor-Equivalence.Ming Xu - 2021 - Studia Logica 109 (6):1177-1200.
Finite Axiomatizability of Transitive Modal Logics of Finite Depth and Width with Respect to Proper-Successor-Equivalence.Yan Zhang & X. U. Ming - forthcoming - Review of Symbolic Logic:1-14.
Modal and guarded characterisation theorems over finite transition systems.Martin Otto - 2004 - Annals of Pure and Applied Logic 130 (1-3):173-205.
A sufficiently fast algorithm for finding close to optimal clique trees.Ann Becker & Dan Geiger - 2001 - Artificial Intelligence 125 (1-2):3-17.
A Tableau Algorithm for the Clique Guarded Fragment.Colin Hirsch & Stephan Tobies - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 257-277.
A Tableau Algorithm for the Clique Guarded Fragment.Colin Hirsch & Stephan Tobies - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 257-277.

Analytics

Added to PP
2013-12-31

Downloads
17 (#896,762)

6 months
7 (#491,177)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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.
Locality and modular Ehrenfeucht–Fraïssé games.Achim Blumensath - 2012 - Journal of Applied Logic 10 (1):144-162.

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