The language of search

Jinbo Huang*, Adnan Darwiche

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

56 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)191-219
Number of pages29
JournalJournal of Artificial Intelligence Research
Volume29
DOIs
Publication statusPublished - 2007
Externally publishedYes

Fingerprint

Dive into the research topics of 'The language of search'. Together they form a unique fingerprint.

Cite this