期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2007
卷号：29
页码：191-219
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：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
