Göm menyn
Files: Description Format
Fulltext PDF (requires Acrobat Reader)
Fulltext part 1 PostScript (requires a PostScript Reader)
  Fulltext part 2 PostScript (requires a PostScript Reader)
   
Author: Alan M. Frisch
Article title: Solving Constraint Satisfaction Problems with NB-Resolution
Publ. type: Article
Volume: 4
Article No: 37
Language: English
Abstract [en]: Though resolution and constraint satisfaction problems are two of the most developed areas in artificial intelligence, little has been done to explore the relationship between the two. This paper explores the relationship using the key observation that semantic trees, used in the study of resolution, and backtrack search spaces, used in the study of constraint satisfaction, are the same objects. The exploration results in the development of the NB-resolution rule of inference, a generalisation of ordinary resolution that can be used to solve constraint satisfaction problems. This paper proves that a clausal-form constraint satisfaction problem is backtrack-free if its constraints are closed under NB-resolution. This generalises the usual completeness result for resolution by telling us not only what happens when an unsatisfiable set of clauses is closed under resolution but also what happens when a satisfiable set of clauses is closed under resolution. The paper also presents a refinement of NB-resolution based on the order in which variables are considered in the search procedure.
Publisher: Linköping University Electronic Press
Year: 1999
Available: 1999-12-30
No. of pages: 14
Series: Linköping Electronic Articles in Computer and Information Science
ISSN: 1401-9841


Responsible for this page: Peter Berkesand
Last updated: 2017-02-21