Answer Set Programming (ASP) is a recent form of declarative programming that has been applied to many knowledge-intensive tasks, such as product configuration, planning, diagnosis, and information integration. Like other computing paradigms, such as SAT (Satisfiability Checking) and CP (Constraint Programming), ASP provides a common basis for formalizing and solving various problems, but is distinct from others in that it focuses on knowledge representation and has proved to be useful for rapid prototyping. While the research on ASP has produced many promising results, it has also identified serious limitations.
The project aims at overcoming the limitations by merging ASP with other computing paradigms, such as satisfiability checking, first-order logic and constraint programming, and exploring the synergy between them. This project is expected to provide a transformative understanding of ASP's relation to other computing paradigms, to enhance ASP's reasoning capability and broaden the areas in which it is effective. Within knowledge representation, the study will clarify the role of ASP as a major knowledge representation formalism with effective computation methods that combines various methods available in other computing paradigms.
Answer Set Programming (ASP) is a declarative programming paradigm oriented towards solving combinatorial and knowledge-intensive problems, such as product configuration, planning, diagnosis, and information integration. It has well-developed foundations, efficient reasoning systems, and a methodology of use tested on a number of applications. However, the original ASP language and its various extensions were limited to the propositional level, and did not account for the needed first-order constructs in ASP languages. Further, the limitation causes an inherent difficulty in combining ASP with other computing paradigms, which is often need in order to overcome the grounding bottleneck of the computation, and to perform expressive first-order nonmonotonic reasoning. Supported by the award, we generalized the stable model semantics to the truly first-order level, and reconstructed the mathematical foundation of ASP based on it. This allowed us to overcome the limitations of the traditional ASP semantics, crossing the boundaries between first-order and propositional reasoning in ASP. Our research also clarified the relationship between ASP and other related computing paradigms, such as propositional satisfiability (SAT), first-order logic (FOL) and constraint processing (CP), as well as providing a way to compute classical logic based formalisms using ASP solvers. We discovered that several knowledge representation formalisms that were thought to be on different, incompatible foundations can be unified through the first-order stable model semantics. The project has led to numerous publications in journals and conferences, two Ph.D. dissertations, and two software systems that were made publicly available. The students involved in the project had chances to present their work at several conferences. An undergraduate student supported by the REU supplement is continuing his graduate study under the PI’s supervision.
