Extending Answer Set Programming

点击翻译按钮获取中文摘要

A computational problem can be solved by designing and implementing an algorithm for it, or by expressing it in an intuitive modelling language that comes with software for evaluating expressions written in the language. The latter is an example of what is called declarative problem solving. The goal of this research is to extend Answer Set Programming (ASP for short), which has emerged as a promising declarative paradigm for solving computational problems, by addressing two important problems: (a) on integrating open-world with closed-world reasoning, and (b) on using ASP as a uniform language for modeling and reasoning with domain as well as defeasible ontological knowledge. ****The main idea of ASP is that a given problem is stated in terms of constraints, which are expressed in a rule-based language under the stable model (also called answer set) semantics. Intuitively, an answer set corresponds to a solution to the problem being solved. When an answer set is computed, the user can extract from it the corresponding solution. The formulation of ASP has been crystallized from years of research in knowledge representation, logic programming, and constraint satisfaction. The goal is to provide a declarative language for modelling domain knowledge and computational tools for processing programs written in such a language. With highly competitive ASP solvers already built, several applications have been developed, for example, in molecular biology, decision support systems, planning and scheduling, solving puzzles and games, and more recently, in reasoning with the Web where ontological knowledge plays a critical role. ****In this research, we propose to study two directions of extending ASP, each with distinguished features and merits. One is on a tight integration of ASP with decidable fragments of class logic, where we will address the problem of combining open and closed world reasoning. These kind of reasoning tasks often arise in the context of reasoning with complex heterogeneous systems. One advantage of this approach is that it allows the adoption of efficient inference engines, e.g., those developed for reasoning with ontology. The other direction concerns ASP with existential rules for representing and reasoning with domain and defeasible ontological knowledge in a uniform language. This will result in a seamless integration of different kinds of reasoning and establish foundations for building the next generation ASP solvers. ***It is well anticipated that many further applications would require processing domain knowledge in conjunction with ontological knowledge, such as planning and scheduling, clinical trial and complex management systems, and reasoning with the Web. The success of this research will provide needed insights, and computational mechanisms, for advancing the ASP adoption in solving the next wave of new applications.******