This book aims to lay bare the logical foundations of tractable reasoning. It draws on Marvin Minsky's seminal work on frames, which has been highly influential in computer science and, to a lesser extent, in cognitive science. Only very few people have explored ideas about frames in logic, which is why the investigation in this book breaks new ground. The apparent intractability of dynamic, inferential reasoning is an unsolved problem in both cognitive science and logic-oriented artificial intelligence. By means of a logical investigation of frames and frame concepts, Andreas devises a novel logic of tractable reasoning, called frame logic. Moreover, he devises a novel belief revision scheme, which is tractable for frame logic. These tractability results shed new light on our logical and cognitive means to carry out dynamic, inferential reasoning. Modularity remains central for tractability, and so the author sets forth a logical variant of the massive modularity hypothesis in cognitive science. This book conducts a sustained and detailed examination of the structure of tractable and intelligible reasoning in cognitive science and artificial intelligence. Working from the perspective of formal epistemology and cognitive science, Andreas uses structuralist notions from Bourbaki and Sneed to provide new foundational analyses of frames, object-oriented programming, belief revision, and truth maintenance. Andreas then builds on these analyses to construct a novel logic of tractable reasoning he calls frame logic, together with a novel belief revision scheme that is tractable for frame logic. Put together, these logical analyses and tractability results provide new understandings of dynamic and inferential reasoning. Jon Doyle, North Carolina State University

In order to specify a limited reasoning service for proper+ KBs, we propose a new logic of limited belief called the subjective logic SL . SL supports unit resolution, but only does case analysis in a limited way. We give a sound and complete axiomatization for propositional SL . Reasoning based on SL is classically sound and is also classically complete in some simple cases. We show that SL -based reasoning with proper+ KBs is decidable in general, and tractable when both the KB and the query use a bounded number of variables. This thesis proposes a general methodology to establish tractable (by "tractable" we mean "solvable in polynomial time") limited reasoning services for incomplete first-order knowledge bases (KBs). It consists of defining a logic that is weaker than classical logic and has two properties: first, the entailment problem can be reduced to the model checking problem for a characteristic model; and second, the model checking problem is tractable for formulas with a bounded number of variables. We show this methodology in action for two forms of incomplete first-order KBs proposed by Levesque and Lakemeyer. One is called proper KBs, and is used for open-world reasoning. The other is called proper+ KBs, and is used for reasoning with disjunctive information. Levesque has proposed a reasoning scheme called V for proper KBs that is classically sound and is also classically complete when the query is in a certain normal form called NF . We prove that V is tractable for queries with a bounded number of variables. We also settle the open problems concerning the expressiveness and succinctness of NF . Then we extend V to reasoning in dynamic systems, and propose a tractable, sound, and sometimes complete solution to the projection problem, that is, determining whether a formula holds after a sequence of actions is performed.

As a whole, the thesis develops a worst-case tractable, guaranteed sound, conditionally complete and empirically high-recall reasoning solution for both static and dynamic ontologies in expressive DLs. Some techniques presented in the thesis can also be used to improve the performance and/or completeness of other existing reasoning solutions. The results can further be generalised and extended to support a wider range of knowledge representation formalisms, especially when a consequence-based algorithm is available.

Dynamic Epistemic Logic is the logic of knowledge change. This book provides various logics to support such formal specifications, including proof systems. Concrete examples and epistemic puzzles enliven the exposition. The book also offers exercises with answers. It is suitable for graduate courses in logic. Many examples, exercises, and thorough completeness proofs and expressivity results are included. A companion web page offers slides for lecturers and exams for further practice.