Programming with Propositional Logic: A New Approach for Answer-Set Programming

Title: Programming with Propositional Logic: A New Approach for Answer-Set Programming

Abstract: This research explores the use of propositional logic and its extensions for answer-set programming. The study introduces a new logic called the extended logic of propositional schemata with Closed World Assumption (PS+), which supports explicit modeling of constraints on set cardinalities. The paper characterizes the class of problems that can be solved by finite PS+ theories and presents an implementation of a programming system based on the logic PS+. The system includes a solver for processing theories in PS+. Encouraging performance results are reported, showing the system to be competitive with smodels, a state-of-the-art answer-set programming system.

Main Research Question: Can propositional logic and its extensions be used effectively for answer-set programming?

Methodology: The study uses a model-based approach to answer-set programming, where models of a finite theory determine problem solutions. The research proposes a new logic, PS+, based on the logic of propositional schemata and the Closed World Assumption. The logic supports explicit modeling of constraints on set cardinalities. The paper describes how to characterize the class of problems that can be solved by finite PS+ theories and how to implement a programming system based on the logic PS+.

Results: The research presents an implementation of a programming system based on the logic PS+. The system includes a solver for processing theories in PS+. The paper reports encouraging performance results, showing the system to be competitive with smodels, a state-of-the-art answer-set programming system.

Implications: The study suggests that propositional logic and its extensions can be used effectively for answer-set programming. The research introduces a new logic, PS+, which supports explicit modeling of constraints on set cardinalities. The implementation of the programming system and the solver for processing theories in PS+ provide practical applications of the proposed approach.

Link to Article: https://arxiv.org/abs/0107028v1 Authors: arXiv ID: 0107028v1