Knowledge compilation and theory approximation

摘要: Computational efficiency is a central concern in the design of knowledge representation systems. In order to obtain efficient systems, it has been suggested that one should limit form statements base or use an incomplete inference mechanism. The former approach often too restrictive for practical applications, whereas latter leads uncertainty about exactly what can and cannot be inferred from base. We present third alternative, which given general language translated (compiled) into tractable form—allowing subsequent query answering.We show how propositional logical theories compiled Horn approximate original information. approximations bound theory below above terms strength. procedures are extended other languages (for example, binary clauses) first-order case. Finally, we demonstrate generality our by compiling concept descriptions frame-based form.