Computer Science – Artificial Intelligence
Scientific paper
2011-10-12
Journal Of Artificial Intelligence Research, Volume 29, pages 191-219, 2007
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.2097
This paper is concerned with a class of algorithms that perform exhaustive search on propositional knowledge bases. We show that each of these algorithms defines and generates a propositional language. Specifically, we show that the trace of a search can be interpreted as a combinational circuit, and a search algorithm then defines a propositional language consisting of circuits that are generated across all possible executions of the algorithm. In particular, we show that several versions of exhaustive DPLL search correspond to such well-known languages as FBDD, OBDD, and a precisely-defined subset of d-DNNF. By thus mapping search algorithms to propositional languages, we provide a uniform and practical framework in which successful search techniques can be harnessed for compilation of knowledge into various languages of interest, and a new methodology whereby the power and limitations of search algorithms can be understood by looking up the tractability and succinctness of the corresponding propositional languages.
Darwiche Adnan
Huang Jianwei
No associations
LandOfFree
The Language of Search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Language of Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Language of Search will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-634473