Constraint satisfaction, irredundant axiomatisability and continuous colouring

DOI10.1007/S11225-012-9372-4MaRDI QIDQ361864zbMATH OpenOpenAlexFDO

Authors Marcel Jackson, Belinda Trotta

Publication date 19 August 2013

Published in Studia Logica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11225-012-9372-4

zbMATH Keywords

constraint satisfaction problemsquasivarietyantivarietygraph dualitiesirredundant axiomatisabilitystandard topological quasivarieties

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07) Quasivarieties (08C15) Applications of model theory (03C98)

Recommendations

• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• The axiomatizability of topological prevarieties
• Meditations on quantified constraint satisfaction
• Logical compactness and constraint satisfaction problems
• A Characterisation of First-Order Constraint Satisfaction Problems

Cites work

• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 3787631 (Why is no real title available?)
• scientific article; zbMATH DE number 1226180 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 2171495 (Why is no real title available?)
• A Characterisation of First-Order Constraint Satisfaction Problems
• Antivarieties and colour-families of graphs.
• Duality theorems for finite structures (characterising gaps and good characterisations)
• EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
• FINITE SEMIGROUPS WITH INFINITE IRREDUNDANT IDENTITY BASES
• Finiteness properties of varieties and the restriction to finite algebras.
• Flat algebras and the translation of universal Horn logic to equational logic
• Homomorphism preservation theorems
• On classes of relations and graphs determined by subobjects and factorobjects
• On digraph coloring problems and treewidth duality
• On pseudovarieties
• On the quasivarieties generated by finite semigroups
• Open questions related to the problem of Birkhoff and Maltsev
• Quasi-equational bases for graphs of semigroups, monoids and groups.
• Residual bounds for compact totally disconnected algebras
• Residual properties of pre-bipartite digraphs
• Residual properties of reflexive, anti-symmetric digraphs
• Residual properties of simple graphs
• Simple compact topological lattices
• Standard topological algebras: syntactic and principal congruences and profiniteness
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The axiomatizability of topological prevarieties
• Theorems on Compact Totally Disconnected Semigroups and Lattices

Cited in

(5)

• Profinite locally finite quasivarieties
• Axiomatisability and hardness for universal Horn classes of hypergraphs
• Relativised homomorphism preservation at the finite level
• Boolean topological graphs of semigroups: the lack of first-order axiomatization
• The axiomatizability of topological prevarieties

This page was built for publication: Constraint satisfaction, irredundant axiomatisability and continuous colouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q361864)