It is known that a countable $\omega $ -categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.

Product configuration is when an artifact from a product family is assembled from a set of predefined components that can only be combined in certain ways. These ways are defined by configuration rules. The product developers inspect the configuration rules when they develop new configuration rules or modify the configuration rules set. The inspection of configuration rules is thereby an important activity to avoid errors in the configuration rules set. Several formulations of constraint satisfaction problems (CSPs) are proposed that facilitate the inspection of configuration rules in propositional logic (IF-THEN, AND, NOT, OR, etc.). Many of the configuration rules are so called production rules; that is, a configuration rule is an IF-THEN expression that fires when the IF condition is met. Several configuration rules build chains that fire during the product configuration. It is therefore important not only to inspect single configuration rules but also to analyze the effect of multiple configuration rules. Formulating the tasks as variations of the CSP can support the inspection activity. More specifically, we address the reformulation of configuration rules, testing of feature variant combinations, and counting of item quantities from an item set. The suggested CSPs are tested on industrial vehicle configuration rules for computational performance. The results show that the time for achieving results from the solving of the CSP is within seconds. Our future work will be to implement the various CSPs into a demonstrator that could be tested by product developers.

This paper gives a brief survey of current research on the complexity of the constraint satisfaction problem over fixed constraint languages.

This paper introduces a new constraint domain for reasoning about data with uncertainty. It extends convex modeling with the notion of p-box to gain additional quantifiable information on the data whereabouts. Unlike existing approaches, the p-box envelops an unknown probability instead of approximating its representation. The p-box bounds are uniform cumulative distribution functions (cdf) in order to employ linear computations in the probabilistic domain. The reasoning by means of p-box cdf-intervals is an interval computation which is exerted on the real domain then it is projected onto the cdf domain. This operation conveys additional knowledge represented by the obtained probabilistic bounds. The empirical evaluation of our implementation shows that, with minimal overhead, the output solution set realizes a full enclosure of the data along with tighter bounds on its probabilistic distributions.

We show that every finite, finitely related algebra in a congruence distributive variety has a near unanimity term operation. As a consequence we solve the near unanimity problem for relational structures: it is decidable whether a given finite set of relations on a finite set admits a compatible near unanimity operation. This consequence also implies that it is decidable whether a given finite constraint language defines a constraint satisfaction problem of bounded strict width.

Functional constraints and bi-functional constraints are an important constraint class in Constraint Programming (CP) systems, in particular for Constraint Logic Programming (CLP) systems. CP systems with finite domain constraints usually employ Constraint Satisfaction Problem(s)-based solvers which use local consistency, for example, arc consistency. We introduce a new approach which is based instead on variable substitution. We obtain efficient algorithms for reducing systems involving functional and bi-functional constraints together with other nonfunctional constraints. It also solves globally any CSP where there exists a variable such that any other variable is reachable from it through a sequence of functional constraints. Our experiments on random problems show that variable elimination can significantly improve the efficiency of solving problems with functional constraints.

We prove that if a finite algebra $\mathbf{A}$ generates a congruence distributive variety, then the subalgebras of the powers of $\mathbf{A}$ satisfy a certain kind of intersection property that fails for finite idempotent algebras that locally exhibit affine or unary behaviour. We demonstrate a connection between this property and the constraint satisfaction problem.

The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence139 (2002) 21–45),which has been designed to solve constraint satisfaction problems (CSP), canbe seen, either (i) as an extension of the classical depth first treesearch algorithm with the introduction of a free choice of the variable towhich to backtrack in case of inconsistency, or (ii) as a localsearch algorithm in the space of the partial consistent variableassignments. or (iii) as a hybridisation between local searchand constraint propagation. Experiments reported in Pralet and Verfailllie (2004) show that some heuristics for the choice of thevariable to which to backtrack behave well on consistent instances andthat other heuristics behave well on inconsistent ones. They show alsothat, despite its a priori incompleteness, decision repair,equipped with some specific heuristics, can solve within a limited timealmost all the consistent and inconsistent randomly generatedinstances over the whole constrainedness spectrum. In this paper, wediscuss the heuristics that could be used by decisionrepair to solve consistent instances, on the one hand, andinconsistent ones, on the other hand. Moreover, we establish thatsome specific heuristics make decision repair complete.

MarCon (Market-based Constraints) applies market-based control to distributed constraint problems. It offers a new approach to distributing constraint problems that avoids challenges faced by current approaches in some problem domains, and it provides a systematic method for applying markets to a wide array of problems. Constraint agents interact with one another via the variable agents in which they have a common interest, using expressions of their preferences over sets of assignments. Each variable integrates this information from the constraints interested in it and provides feedback that enables the constraints to shrink their sets of assignments until they converge on a solution. MarCon originated in a system for supporting human product designers, and its mechanisms are particularly useful for applications integrating human and machine intelligence to explore implicit constraints. MarCon has been tested in the domain of mechanical design, in which its set-narrowing process is particularly useful.

One of the main difficulties with configuration problem solving lies in the representation of the domain knowledge because many different aspects, such as taxonomy, topology, constraints, resource balancing, component generation, etc., have to be captured in a single model. This model must be expressive, declarative, and structured enough to be easy to maintain and to be easily used by many different kind of reasoning algorithms. This paper presents a new framework where a configuration problem is considered both as a classification problem and as a constraint satisfaction problem (CSP). Our approach deeply blends concepts from the CSP and object-oriented paradigms to adopt the strengths of both. We expose how we have integrated taxonomic reasoning in the constraint programming schema. We also introduce new constrained variables with nonfinite domains to deal with the fact that the set of components is previously unknown and is constructed during the search for solution. Our work strongly focuses on the representation and the structuring of the domain knowledge, because the most common drawback of previous works is the difficulty to maintain the knowledge base that is due to a lack of structure and expressiveness of the knowledge representation model. The main contribution of our work is to provide an object-oriented model completely integrated in the CSP schema, with inheritance and classification mechanisms, and with specific arc consistency algorithms.