Loading...
Please wait, while we are loading the content...
Similar Documents
Checking termination of bottom-up evaluation of logic programs with function symbols
| Content Provider | Scilit |
|---|---|
| Author | Calautti, Marco Greco, Sergio Spezzano, Francesca Trubitsyna, Irina |
| Copyright Year | 2014 |
| Description | Recently, there has been an increasing interest in the bottom-up evaluation of the semantics of logic programs with complex terms. The presence of function symbols in the program may render the ground instantiation infinite, and finiteness of models and termination of the evaluation procedure, in the general case, are not guaranteed anymore. Since the program termination problem is undecidable in the general case, several decidable criteria (called program termination criteria) have been recently proposed. However, current conditions are not able to identify even simple programs, whose bottom-up execution always terminates. The paper introduces new decidable criteria for checking termination of logic programs with function symbols under bottom-up evaluation, by deeply analyzing the program structure. First, we analyze the propagation of complex terms among arguments by means of the extended version of the argument graph calledpropagation graph. The resulting criterion, calledacyclicity, generalizes most of the decidable criteria proposed so far. Next, we study how rules may activate each other and define a more powerful criterion, calledsafety. This criterion uses the so-calledsafety functionable to analyze how rules may activate each other and how the presence of some arguments in a rule limits its activation. We also study the application of the proposed criteria to bound queries and show that the safety criterion is well-suited to identify relevant classes of programs and bound queries. Finally, we propose a hierarchy of classes of terminating programs, calledk-safety, where thek-safe class strictly includes the (k-1)-safe class. |
| Related Links | http://arxiv.org/pdf/1407.2106 http://arxiv.org/abs/1407.2106 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/B22F50538C075580BE372AFBC0FE24D5/S1471068414000623a.pdf/div-class-title-checking-termination-of-bottom-up-evaluation-of-logic-programs-with-function-symbols-a-href-fn1a-ref-type-fn-a-div.pdf |
| Ending Page | 889 |
| Page Count | 36 |
| Starting Page | 854 |
| ISSN | 14710684 |
| e-ISSN | 14753081 |
| DOI | 10.1017/s1471068414000623 |
| Journal | Theory and Practice of Logic Programming |
| Issue Number | 6 |
| Volume Number | 15 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2015-11-01 |
| Access Restriction | Open |
| Subject Keyword | Theory and Practice of Logic Programming Logic Programming with Function Symbols up Execution Program Termination Stable Models |
| Content Type | Text |
| Resource Type | Article |
| Subject | Artificial Intelligence Theoretical Computer Science Computational Theory and Mathematics Hardware and Architecture Software |
