|
|||||
|
|
Equivalence of propositional Prolog programs |
|
| Authors: | Hans Kleine Büning Ulrich Löwen Stefan Schmitgen |
| Affiliation: | (1) FB 11-Praktische Informatik, Universität-GH-Duisburg, Postfach 10 16 29, D-4100 Duisburg 1, West Germany |
| Abstract: | We show that the equivalence problem for propositional Prolog programs is coNP-complete. Considering yes-no answers only the modified equivalence problem is solvable in polynomial time. Furthermore, the problem whether a program does not terminate for some question is NP-complete. For a fixed question the loop problem can be decided in linear time.The work of this author was supported by the Studienstiftung des Deutschen Volkes. |
| Keywords: | Propositional logic programs Prolog inference strategy complexity of inference loop detection equivalence of Prolog programs complexity of equivalence |
| 本文献已被 SpringerLink 等数据库收录！ | |