Towards Average Complexity of Propositional Binary Prolog Programs
Hans Kleine Büning, Ulrich Löwen · Fundamenta Informaticae · 1990
We investigate the average complexity of various classes of binary propositional Prolog programs. We consider classes of tree-like programs introducing a concept of unary and binary edges in a tree to manage situations where a consequence A ← B of a Prolog program can be derived in several ways. We establish exponential lower bounds for the average complexity of tree-like Prolog programs having no facts and we have polynomial upper bounds for various classes of tree-like Prolog programs with facts. These results should be considered as a first step towards the average complexity of propositional Prolog programs.