Towards Average Complexity of Propositional Binary Prolog Programs

Article type: Research Article

Authors: Kleine Büning, Hans | Löwen, Ulrich^{; *}

Affiliations: FB 11-Praktische Informatik, Universität Duisburg, D-4100 Duisburg 1, F.R. Germany

Note: [*] The work of the author was supported by the Studienstiftung des Deutschen Volkes.

Abstract: 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.

DOI: 10.3233/FI-1990-13309

Journal: Fundamenta Informaticae, vol. 13, no. 3, pp. 387-399, 1990