Constraint satisfaction, irredundant axiomatisability and continuous colouring

DOI10.1007/S11225-012-9372-4zbMATH Open1294.03021OpenAlexW2026679370MaRDI QIDQ361864FDOQ361864

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

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

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)

Cites Work

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

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)