Using model generation theorem provers for the computation of answer sets

Download
2009
Sabuncu, Orkunt
Answer set programming (ASP) is a declarative approach to solving search problems. Logic programming constitutes the foundation of ASP. ASP is not a proof-theoretical approach where you get solutions by answer substitutions. Instead, the problem is represented by a logic program in such a way that models of the program according to the answer set semantics correspond to solutions of the problem. Answer set solvers (Smodels, Cmodels, Clasp, and Dlv) are used for finding answer sets of a given program. Although users can write programs with variables for convenience, current answer set solvers work on ground logic programs where there are no variables. The grounding step of ASP generates a propositional instance of a logic program with variables. It may generate a huge propositional instance and make the search process of answer set solvers more difficult. Model generation theorem provers (Paradox, Darwin, and FM-Darwin) have the capability of producing a model when the first-order input theory is satisfiable. This work proposes the use of model generation theorem provers as computational engines for ASP. The main motivation is to eliminate the grounding step of ASP completely or to perform it more intelligently using the model generation system. Additionally, regardless of grounding, model generation systems may display better performance than the current solvers. The proposed method can be seen as lifting SAT-based ASP, where SAT solvers are used to compute answer sets, to the first-order level for tight programs. A completion procedure which transforms a logic program to formulas of first-order logic is utilized. Besides completion, other transformations which are necessary for forming a firstorder theory suitable for model generation theorem provers are investigated. A system called Completor is implemented for handling all the necessary transformations. The empirical results demonstrate that the use of Completor and the theorem provers together can be an e ective way of computing answer sets. Especially, the run time results of Paradox in the experiments has showed that using Completor and Paradox together is favorable compared to answer set solvers. This advantage has been more clearly observed for programs with large propositional instances, since grounding can be a bottleneck for such programs.

Suggestions

Using Criticalities as a Heuristic for Answer Set Programming
SABUNCU, ORKUNT; Alpaslan, Ferda Nur; AKMAN, VAROL (2004-01-08)
Answer Set Programming is a new paradigm based on logic programming. The main component of answer set programming is a system that finds the answer sets of logic programs. During the computation of an answer set, systems are faced with choice points where they have to select a literal and assign it a truth value. Generally, systems utilize some heuristics to choose new literals at the choice points. The heuristic used is one of the key factors for the performance of the system. A new heuristic for answer s...
Multi-objective integer programming: A general approach for generating all non-dominated solutions
Oezlen, Melih; Azizoğlu, Meral (Elsevier BV, 2009-11-16)
In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical epsilon-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical epsilon-constraint method on the bi-objective integer programming problem for the sake of comple...
On Verification of Restricted Extended Affine Equivalence of Vectorial Boolean Functions
Özbudak, Ferruh; Yayla, Oğuz (2015-02-01)
Vectorial Boolean functions are used as substitution boxes in cryptosystems. Designing inequivalent functions resistant to known attacks is one of the challenges in cryptography. In doing this, finding a fast technique for determining whether two given functions are equivalent is a significant problem. A special class of the equivalence called restricted extended affine (REA) equivalence is studied in this paper. We update the verification procedures of the REA-equivalence types given in the recent work of ...
A multiple criteria sorting approach based on distance functions
Çelik, Bilge; Karasakal, Esra; İyigün, Cem; Department of Industrial Engineering (2011)
Sorting is the problem of assignment of alternatives into predefined ordinal classes according to multiple criteria. A new distance function based solution approach is developed for sorting problems in this study. The distance to the ideal point is used as the criteria disaggregation function to determine the values of alternatives. These values are used to sort them into the predefined classes. The distance function is provided in general distance norm. The criteria disaggregation function is determined ac...
A flexible approach to ranking with an application to MBA Programs
Köksalan, Mustafa Murat; Buyukbasaran, Tayyar; Ozpeynirci, Oezguer; Wallenius, Jyrki (Elsevier BV, 2010-03-01)
We develop a model for flexibly ranking multi-dimensional alternatives/units into preference classes via Mixed Integer Programming. We consider a linear aggregation model, but allow the criterion weights to vary within pre-specified ranges. This allows the individual alternatives/units to play to their strengths. We illustrate the use of the model by considering the Financial Times Global MBA Program rankings and discuss the implications. We argue that in many applications neither the data nor the weights o...
Citation Formats
O. Sabuncu, “Using model generation theorem provers for the computation of answer sets,” Ph.D. - Doctoral Program, Middle East Technical University, 2009.