Disjunctive ASP with Functions: Decidable Queries and Effective Computation

Details Disjunctive ASP with Functions: Decidable Queries and Effective Computation Disjunctive ASP with Functions: Decidable Queries and Effective Computation

2010-07-22

arxiv.org/abs/1007.4028v1

Theory and Practice of Logic Programming, 10(4-6): 497-512, 2010

Computer Science

Logic in Computer Science

16 pages, 1 figure

Scientific paper

10.1017/S1471068410000244

Querying over disjunctive ASP with functions is a highly undecidable task in general. In this paper we focus on disjunctive logic programs with stratified negation and functions under the stable model semantics (ASP^{fs}). We show that query answering in this setting is decidable, if the query is finitely recursive (ASP^{fs}_{fr}). Our proof yields also an effective method for query evaluation. It is done by extending the magic set technique to ASP^{fs}_{fr}. We show that the magic-set rewritten program is query equivalent to the original one (under both brave and cautious reasoning). Moreover, we prove that the rewritten program is also finitely ground, implying that it is decidable. Importantly, finitely ground programs are evaluable using existing ASP solvers, making the class of ASP^{fs}_{fr} queries usable in practice.

Affiliated with

Also associated with

No associations

Rating

Disjunctive ASP with Functions: Decidable Queries and Effective Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Disjunctive ASP with Functions: Decidable Queries and Effective Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Disjunctive ASP with Functions: Decidable Queries and Effective Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-138391