Search

This special issue is dedicated to John McCarthy, founding father of Artificial Intelligence. It contains a collection of recent contributions to the field of knowledge representation and reasoning, a field that McCarthy founded and that has been a main focus of his research during the last half century. In this introductory article, we survey some of McCarthy's major contributions to the field of knowledge representation and reasoning, and situate the papers in this special issue in the context of McCarthy's previous work.

In this paper we show how tree decomposition can be applied to reasoning with first-order and propositional logic theories. Our motivation is two-fold. First, we are concerned with how to reason effectively with multiple knowledge bases that have overlap in content. Second, we are concerned with improving the efficiency of reasoning over a set of logical axioms by partitioning the set with respect to some detectable structure, and reasoning over individual partitions either locally or in a distributed fashion. To this end, we provide algorithms for partitioning and reasoning with related logical axioms in propositional and first-order logic.Many of the reasoning algorithms we present are based on the idea of passing messages between partitions. We present algorithms for both forward (data-driven) and backward (query-driven) message passing. Different partitions may have different associated reasoning procedures. We characterize a class of reasoning procedures that ensures completeness and soundness of our message-passing algorithms. We further provide a specialized algorithm for propositional satisfiability checking with partitions. Craig's interpolation theorem serves as a key to proving soundness and completeness of all of these algorithms. An analysis of these algorithms emphasizes parameters of the partitionings that influence the efficiency of computation. We provide a greedy algorithm that automatically decomposes a set of logical axioms into partitions, following this analysis.

Reformulation is ubiquitous in problem solving and is especially common in modeling physical systems. In this paper we examine reformulation techniques in the context of reasoning about physical systems. This paper does not present a general theory of reformulation, but it studies a number of known reformulation techniques to achieve a broad understanding of the space of available reformulations. In doing so, we present a practical framework for specifying, classifying, and evaluating various reformulation techniques applicable to this class of problems. Our framework provides the terminology to specify the conditions under which a particular reformulation technique is applicable, the cost associated with performing the reformulation, and the effects of the reformulation with respect to the problem encoding.