Constraint Satisfaction, Irredundant Axiomatisability and Continuous Colouring

Studia Logica 101 (1):65-94 (2013)
  Copy   BIBTEX

Abstract

We observe a number of connections between recent developments in the study of constraint satisfaction problems, irredundant axiomatisation and the study of topological quasivarieties. Several restricted forms of a conjecture of Clark, Davey, Jackson and Pitkethly are solved: for example we show that if, for a finite relational structure M, the class of M-colourable structures has no finite axiomatisation in first order logic, then there is no set (even infinite) of first order sentences characterising the continuously M-colourable structures amongst compact totally disconnected relational structures. We also refute a rather old conjecture of Gorbunov by presenting a finite structure with an infinite irredundant quasi-identity basis

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,486

External links

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

Through your library

Analytics

Added to PP
2012-06-12

Downloads
45 (#525,137)

6 months
8 (#432,306)

Historical graph of downloads
How can I increase my downloads?