Constraint inference

In constraint satisfaction, constraint inference is a relationship between constraints and their consequences. A set of constraints D entails a constraint C if every solution to D is also a solution to C. In other words, if V is a valuation of the variables in the scopes of the constraints in D and all constraints in D are satisfied by V, then V also satisfies the constraint C.

Some operations on constraints produce a new constraint that is a consequence of them. Constraint composition operates on a pair of binary constraints ((x,y),R) and ((y,z),S) with a common variable. The composition of such two constraints is the constraint ((x,z),Q) that is satisfied by every evaluation of the two non-shared variables for which there exists a value of the shared variable y such that the evaluation of these three variables satisfies the two original constraints ((x,y),R) and ((y,z),S).

Constraint projection restricts the effects of a constraint to some of its variables. Given a constraint (t,R) its projection to a subset t' of its variables is the constraint (t',R') that is satisfied by an evaluation if this evaluation can be extended to the other variables in such a way the original constraint (t,R) is satisfied.

Extended composition is similar in principle to composition, but allows for an arbitrary number of possibly non-binary constraints; the generated constraint is on an arbitrary subset of the variables of the original constraints. Given constraints $C_1,\ldots,C_m$ and a list A of their variables, the extended composition of them is the constraint (A,R) where an evaluation of A satisfies this constraint if it can be extended to the other variables so that $C_1,\ldots,C_m$ are all satisfied.

See also

• Constraint satisfaction problem

References

• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. http://www.ics.uci.edu/~dechter/books/index.html.  ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press.  ISBN 0-521-82583-0
• Marriot, Kim; Peter J. Stuckey (1998). Programming with constraints: An introduction. MIT Press.  ISBN 0-262-13341-5

This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Constraint programming Inference Applied mathematics stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем написать реферат Mylswamy Annadurai Trotton Look at other dictionaries: Constraint logic programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia Hybrid algorithm (constraint satisfaction) — In constraint satisfaction, a hybrid algorithm solves a constraint satisfaction problem by the combination of two different methods, for example variable conditioning (backtracking, backjumping, etc.) and constraint inference (arc consistency,… …   Wikipedia Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… …   Wikipedia Constrained Conditional Models — A Constrained Conditional Model (CCM) is a machine learning and inference framework that augments the learning of conditional (probabilistic or discriminative) models with declarative constraints. The constraint can be used as a way to… …   Wikipedia Inquiry — For other uses, see Public inquiry and Enquiry character. An inquiry is any process that has the aim of augmenting knowledge, resolving doubt, or solving a problem. A theory of inquiry is an account of the various types of inquiry and a treatment …   Wikipedia Principle of maximum entropy — This article is about the probability theoretic principle. For the classifier in machine learning, see maximum entropy classifier. For other uses, see maximum entropy (disambiguation). Bayesian statistics Theory Bayesian probability Probability… …   Wikipedia 2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… …   Wikipedia Comparison of C Sharp and Java — The correct title of this article is Comparison of C# and Java. The substitution or omission of the # sign is because of technical restrictions. Programming language comparisons General comparison Basic syntax Basic instructions …   Wikipedia Info-gap decision theory — is a non probabilistic decision theory that seeks to optimize robustness to failure – or opportuneness for windfall – under severe uncertainty,[1][2] in particular applying sensitivity analysis of the stability radius type[3] to perturbations in… …   Wikipedia Charles Peirce — Infobox Scientist name = Charles Peirce box width = image size = 200px caption = Charles Peirce birth date = September 10, 1839 birth place = Cambridge, Massachusetts death date = April 19, 1914 death place = residence = citizenship = nationality …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”