The complexity of equality constraint languages
type: Item
instance of: scholarly article
title: The complexity of equality constraint languages
zbMATH Open document ID: 1148.68025
author: Manuel Bodirsky
author: Jan Kára
published in: Theory of Computing Systems
publication date: 2008-06-17T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 08A70
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5288694
zbMATH Keywords: Constraint satisfaction
zbMATH Keywords: Logic in computer science
zbMATH Keywords: Computational complexity
zbMATH Keywords: Clones on infinite domains
MaRDI profile type: Publication
full work available at URL: s00224-007-9083-9
OpenAlex ID: W2087215337
cites work: The complexity of satisfiability problems: Refining Schaefer's theorem
cites work: Constraint Satisfaction Problems with Infinite Templates
cites work: Datalog and Constraint Satisfaction with Infinite Templates
cites work: The Complexity of Equality Constraint Languages
cites work: Constraint Satisfaction with Countable Homogeneous Templates
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Q3995219
cites work: Building tractable disjunctive constraints
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Local and global relational consistency
cites work: `` Strong '' NP-Completeness Results
cites work: Closed systems of functions and predicates
cites work: The maximal clones on countable sets that include all permutations.
cites work: Q4336034
cites work: Reasoning about temporal relations
cites work: Q4861481
cites work: Maximal clones on uncountable sets that include all permutations
cites work: Q5478078
cites work: Q3739181
cites work: NP is as easy as detecting unique solutions
DOI: 10.1007/S00224-007-9083-9
description: scientific article; zbMATH DE number 5288694