The comparative linguistics of knowledge representation

Abstract

We develop a methodology for comparing knowledge representation formalisms in terms of their "representational succinctness," that is, their ability to express knowledge situations relatively efficiently. We use this framework for comparing many important formalisms for knowledge base representation: propositional logic, default logic, circumscription, and model preference defaults; and, at a lower level, Horn formulas, characteristic models, decision trees, disjunctive normal form, and conjunctive normal form. We also show that adding new variables improves the effective expressibility of certain knowledge representation formalisms. 1 Introduction Many important knowledge representation formalisms have been proposed, used, and studied during the past fifteen years, including various forms of propositional logic, nonmonotonic formalisms, decision trees, and so on. There is now a host of methods available for representing complex knowledge, and for reasoning about it. An interesting qu...