The proposed research touches on both theoretical computer science and artifcial intelligence (AI). In particular, the techniques of theoretical computer science will be applied to two significant problem areas in AI: knowledge representation and machine learning. Certain forms of knowledge representation are extremely important for AI applications. Some, such as conjunctions of Horn clauses, have been studied from AI's earliest days; others, such as decomposable negation normal form (DNNF), are relatively new. This project will study the computational complexity aspects of these and other forms of knowledge representation, and formal learnability results for them. Knowledge representation is interesting because the choice of representation determines the ease or difficulty of various tasks that an intelligent agent must perform, such as reasoning or planning. The representations of interest for this research include various forms of propositional logic, ranging from disjunctive normal form to DNNF, and various more powerful logics, such as modal logics, some forms of predicate logic, and probabilistic description logic. This proposal includes a variety of problems and approaches, unified by recurring themes drawn from combinatorics and logic. One main goal of the proposed work is to advance the understanding of several aspects of im- portant knowledge representation formalisms. This includes answering questions on expressiveness for both basic formalisms such as disjunctive normal forms and decision trees, and also for recent formalisms such as DNNFs. It also includes determining the complexity of handling exceptions in different formalisms, which is both a practical problem and is also closely related to some questions on the efficient learnability of the representations. The proposed work will include a probabilistic analysis of the important reasoning technique of Horn approximations, in order to identify situ- ations when the method can be expected to work efficiently in spite of examples demonstrating its worst-case behavior, and an analysis of the possibilities for compiling a knowledge bases into a more efficient form having short resolution proofs of its consequences. Another goal of the project is to obtain a better integration of the learnability aspect of the different knowledge representation formalisms into the emerging comparative theory of knowledge representation. This line of research includes making new progress on old, well established problems, such as learning Horn sentences, the further study of recently introduced problems, such as revising Horn sentences, and the exploration of representations that have not been studied yet from the point of view of learnability, such as modal logics. Work is also proposed on the exclusion dimension, a promising recent notion, in both propositional and predicate logic. Intellectual merit: The proposal addresses several key issues in knowledge representation and learning: expressiveness, efficient manipulation, efficient reasoning, and efficient learning and revision, in propositional, predicate, and modal logic. The proposal builds on the previous re- search results of the proposers, which includes the development of new approaches to logic learning and theory revision, and their technical expertise in computational learning theory, computational complexity theory, combinatorics and logic, leading up to a comprehensive, in-depth study of core problem areas of artificial intelligence, emphasizing the interactions between the different aspects. The proposers have initial results in several of the suggested research directions. Broader impact: The rapid increase in both the amount of, and the inherent complexity of data greatly increases the importance of expressive knowledge representation formalisms that are suitable for efficient manipulation, reasoning, automated acquisition and revision. Symbolic knowledge representation formalisms based on propositional, predicate, modal and other logics form an indispensable component in a large number of applications. Understanding the complexity obstacles in these applications, and identifying possible avenues for circumventing them, is a crucial component of further development.
