Evaluation of answer set programs with bounded predicate arities

Abstract

We consider the class of logic programs under the restriction of bounded predicate arities.<br />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.<br />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.<br />