Title: Evaluation of answer set programs with bounded predicate arities
Language: English
Authors: Mushthofa, Mushthofa 
Qualification level: Diploma
Keywords: logic; answer set; semantics; evaluation; solver; complexity
logic; answer set; semantics; evaluation; solver; complexity
Advisor: Eiter, Thomas 
Issue Date: 2009
Number of Pages: 105
Qualification level: Diploma
We consider the class of logic programs under the restriction of bounded predicate arities.
Previous results showed that the complexity answer set semantics for such class of logic programs is lower than unrestricted programs. In particular, evaluation under answer set semantics is possible within polynomial space. However, current ASP solvers and grounders do not seem to respect this complexity bound, and may produce exponential size ground programs, even for programs with bounded predicate arities. We present three methods for evaluation of logic programs with bounded predicate arities which stays within polynomial space. We developed an evaluation framework built on top of current ASP solvers based on the methods, and also provided a prototype implementation of the framework.
An experiment was conducted to measure the feasibility and performance of the methods, and to compare it with current ASP solvers, DLV and claspD. The test results showed that the proposed methods and framework are able to evaluate many test instances more efficiently than DLV and claspD. Evaluations by the prototype system stay within polynomial space, and hence, avoid the bottleneck associated with exponential size grounding.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-36890
Library ID: AC07452379
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

checked on Feb 18, 2021


checked on Feb 18, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.