Name
Abstract | ||
|---|---|---|
In this paper, we propose a translation from normal first-order logic programs under the stable model semantics to first-order sentences on finite structures. The translation is done through, what we call, ordered completion which is a modification of Clark@?s completion with some auxiliary predicates added to keep track of the derivation order. We show that, on finite structures, classical models of the ordered completion of a normal logic program correspond exactly to the stable models of the program. We also extend this result to normal programs with constraints and choice rules. From a theoretical viewpoint, this work clarifies the relationships between normal logic programming under the stable model semantics and classical first-order logic. It follows that, on finite structures, every normal program can be defined by a first-order sentence if new predicates are allowed. This is a tight result as not every normal logic program can be defined by a first-order sentence if no extra predicates are allowed or when infinite structures are considered. Furthermore, we show that the result cannot be extended to disjunctive logic programs, assuming that NPcoNP. From a practical viewpoint, this work leads to a new type of ASP solver by grounding on a program@?s ordered completion instead of the program itself. We report on a first implementation of such a solver based on several optimization techniques. Our experimental results show that our solver compares favorably to other major ASP solvers on the Hamiltonian Circuit program, especially on large domains. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.artint.2011.11.001 | Artificial Intelligence |
Keywords | DocType | Volume |
ordered completion,first-order sentence,normal program,stable model semantics,normal logic program,classical first-order logic,hamiltonian circuit program,normal first-order logic program,normal logic programming,finite structure,logic program,first order logic,logic programming,answer set programming | Conference | 177-179, |
Issue | ISSN | Citations |
1 | 0004-3702 | 19 |
PageRank | References | Authors |
0.82 | 23 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vernon Asuncion | 1 | 28 | 4.14 |
| Fangzhen Lin | 2 | 1959 | 196.02 |
| Yan Zhang | 3 | 777 | 123.70 |
| Yi Zhou | 4 | 161 | 26.62 |