An algebraic approach to multi-sorted constraints

An algebraic approach to multi-sorted constraints

Show other versions (1)

Most previous theoretical study of the complexity of the constraint satisfaction problem has considered a simplified version of the problem in which all variables have the same domain. We show here that this apparently minor simplification can in fact change the complexity of the problem, and hence...

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	Bulatov, A, Jeavons, P
Format:	Journal article
Sprog:	English
Udgivet:	2003

Lignende værker

An algebraic approach to multi−sorted constraints
af: Bulatov, A, et al.
Udgivet: (2003)

The Complexity of Constraint Satisfaction: An Algebraic Approach
af: Krokhin, A, et al.
Udgivet: (2004)

Constraint satisfaction problems and finite algebras
af: Bulatov, A, et al.
Udgivet: (2000)

Constraint satisfaction problems and finite algebras
af: Bulatov, A, et al.
Udgivet: (2000)

Classifying the complexity of constraints using finite algebras
af: Bulatov, A, et al.
Udgivet: (2005)

Classifying the complexity of constraints using finite algebras
af: Bulatov, A, et al.
Udgivet: (2005)

Algebraic structures in combinatorial problems
af: Bulatov, A, et al.
Udgivet: (2001)

Constraints and Universal Algebra
af: P.G.Jeavons, et al.
Udgivet: (1998)

Tractable constraints closed under a binary operation
af: Bulatov, A, et al.
Udgivet: (2000)

An algebraic characterisation of complexity for valued constraints
af: Cohen, D, et al.
Udgivet: (2006)

Structural Theory of Automata‚ Semigroups‚ and Universal Algebra
af: Krokhin, A, et al.
Udgivet: (2003)

An algebraic characterisation of complexity for valued constraints
af: Cohen, D, et al.
Udgivet: (2006)

The complexity of maximal constraint languages
af: Bulatov, A, et al.
Udgivet: (2001)

The complexity of maximal constraint languages
af: Bulatov, A, et al.
Udgivet: (2001)

Finite semigroups imposing tractable constraints
af: Bulatov, A, et al.
Udgivet: (2002)

Quantified constraints: Algorithms and complexity
af: Borner, F, et al.
Udgivet: (2003)

Quantified constraints: algorithms and complexity
af: Börner, F, et al.
Udgivet: (2003)

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
af: Krokhin, A, et al.
Udgivet: (2003)

Functions of multiple−valued logic and the complexity of constraint satisfaction: A short survey
af: Krokhin, A, et al.
Udgivet: (2003)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection.
af: Cohen, D, et al.
Udgivet: (2011)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
af: Cohen, D, et al.
Udgivet: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
af: Cohen, D, et al.
Udgivet: (2011)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
af: Cohen, D, et al.
Udgivet: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
af: Cohen, D, et al.
Udgivet: (2011)

A Method to Translate Order-Sorted Algebras to Many-Sorted Algebras
af: Liyi Li, et al.
Udgivet: (2018-02-01)

The complexity of constraint satisfaction games and QCSP
af: Boerner, F, et al.
Udgivet: (2009)

The complexity of constraint satisfaction games and QCSP
af: Börner, F, et al.
Udgivet: (2009)

Synthesis of models for order-sorted first-order theories using linear algebra and constraint solving
af: Salvador Lucas
Udgivet: (2015-12-01)

Presenting Constraints
af: Jeavons, P
Udgivet: (2009)

Presenting Constraints
af: Jeavons, P
Udgivet: (2009)

On The Algebraic Structure Of Combinatorial Problems
af: P.G.Jeavons
Udgivet: (1998)

Constructing constraints
af: P.G.Jeavons
Udgivet: (1998)

On the Directly and Subdirectly Irreducible Many-Sorted Algebras
af: Climent Vidal J., et al.
Udgivet: (2015-03-01)

Injective hulls of many-sorted ordered algebras
af: Zhang Xia, et al.
Udgivet: (2019-12-01)

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
af: Barnaby Martin, et al.
Udgivet: (2012-09-01)

Perfect Constraints Are Tractable
af: Salamon, A, et al.
Udgivet: (2008)

Perfect Constraints Are Tractable
af: Salamon, A, et al.
Udgivet: (2008)

Tractable valued constraints
af: Jeavons, P, et al.
Udgivet: (2012)

Expressibility of valued constraints
af: Živný, S, et al.
Udgivet: (2007)

Tractable Valued Constraints
af: Jeavons, P, et al.
Udgivet: (2013)