The logic of constraint satisfaction Export

@article{csp_logic_mackworth, abstract = {The constraint satisfaction problem (CSP) formalization has been a productive tool within Artificial Intelligence and related areas. The finite CSP (FCSP) framework is presented here as a restricted logical calculus within a space of logical representation and reasoning systems. FCSP is formulated in a variety of logical settings: theorem proving in first order predicate calculus, propositional theorem proving (and hence SAT), the Prolog and Datalog approaches, constraint network algorithms, a logical interpreter for networks of constraints, the constraint logic programming (CLP) paradigm and propositional model finding (and hence SAT, again). Several standard, and some not-so-standard, logical methods can therefore be used to solve these problems. By doing this we obtain a specification of the semantics of the common approaches. This synthetic treatment also allows algorithms and results from these disparate areas to be imported, and specialized, to FCSP; the special properties of FCSP are exploited to achieve, for example, completeness and to improve efficiency. It also allows export to the related areas. By casting CSP both as a generalization of FCSP and as a specialization of CLP it is observed that some, but not all, FCSP techniques lift to CSP and thereby to CLP. Various new connections are uncovered, in particular between the proof-finding approaches and the alternative model-finding approaches that have arisen in depiction and diagnosis applications.}, author = {Mackworth, Alan K.}, citeulike-article-id = {1789704}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/0004-3702(92)90003-G}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/000437029290003G}, citeulike-linkout-2 = {http://www.sciencedirect.com/science/article/B6TYF-47YRKB8-1B/2/edbf302557d745569999f35af81e152b}, doi = {10.1016/0004-3702(92)90003-G}, issn = {00043702}, journal = {Artificial Intelligence}, keywords = {csp, logic, sat}, month = {December}, number = {1-3}, pages = {3--20}, posted-at = {2009-10-21 17:56:19}, priority = {3}, title = {The logic of constraint satisfaction}, url = {http://dx.doi.org/10.1016/0004-3702(92)90003-G}, volume = {58}, year = {1992} }

TY - JOUR ID - csp_logic_mackworth L3 - citeulike-article-id:1789704 N2 - The constraint satisfaction problem (CSP) formalization has been a productive tool within Artificial Intelligence and related areas. The finite CSP (FCSP) framework is presented here as a restricted logical calculus within a space of logical representation and reasoning systems. FCSP is formulated in a variety of logical settings: theorem proving in first order predicate calculus, propositional theorem proving (and hence SAT), the Prolog and Datalog approaches, constraint network algorithms, a logical interpreter for networks of constraints, the constraint logic programming (CLP) paradigm and propositional model finding (and hence SAT, again). Several standard, and some not-so-standard, logical methods can therefore be used to solve these problems. By doing this we obtain a specification of the semantics of the common approaches. This synthetic treatment also allows algorithms and results from these disparate areas to be imported, and specialized, to FCSP; the special properties of FCSP are exploited to achieve, for example, completeness and to improve efficiency. It also allows export to the related areas. By casting CSP both as a generalization of FCSP and as a specialization of CLP it is observed that some, but not all, FCSP techniques lift to CSP and thereby to CLP. Various new connections are uncovered, in particular between the proof-finding approaches and the alternative model-finding approaches that have arisen in depiction and diagnosis applications. IS - 1-3 JF - Artificial Intelligence SN - 00043702 EP - 20 TI - The logic of constraint satisfaction VL - 58 SP - 3 KW - csp KW - logic KW - sat AU - Mackworth, Alan PY - 1992/12// UR - http://dx.doi.org/10.1016/0004-3702(92)90003-G ER -