Abstract
Propositional greatest lower bounds (GLBs) are logically‐defined approximations of a knowledge base. They were defined in the context of Knowledge Compilation, a technique developed for addressing high computational cost of logical inference. A GLB allows for polynomial‐time complete on‐line reasoning, although soundness is not guaranteed. In this paper we propose new algorithms for the generation of a GLB. Furthermore, we give precise characterization of the computational complexity of the problem of generating such lower bounds, thus addressing in a formal way the question “how many queries are needed to amortize the overhead of compilation?”
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Y. Boufkhad, Algorithms for propositional KB approximation, in: Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI'98) (1998) pp. 280-285.
Y. Boufkhad, É. Grégoire, P. Marquis, B. Mazure and L. Saïs, Tractable cover compilations, in: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI'97) (1997) pp. 122-127.
M. Cadoli, Semantical and computational aspects of Horn approximations, in: Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI'93) (1993) pp. 39-44.
M. Cadoli and F.M. Donini, A survey on knowledge compilation, AI Communications — The European Journal for Artificial Intelligence 10 (1997) 137-150.
M. Cadoli, L. Palopoli and F. Scarcello, Propositional lower bounds: Generalization and algorithms, in: Proceedings of the Sixth European Workshop on Logics in Artificial Intelligence (JELIA'98), Lecture Notes in Artificial Intelligence, Vol. 1489 (Springer-Verlag, 1998) pp. 355-367.
M. Conforti and G. Cornuéjols, A class of logic problems solvable by linear programming, Journal of the ACM 42 (1995) 1107-1113.
A. del Val, An analysis of approximate knowledge compilation, in: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI'95) (1995) pp. 830-836.
W.P. Dowling and J.H. Gallier, Linear-time algorithms for testing the satisfiability of propositional Horn formulae, Journal of Logic Programming 1 (1984) 267-284.
G. Gogic, C. Papadimitriou and M. Sideri, Incremental recompilation of knowledge, in: Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI'94) (1994) pp. 922-927.
L. Henschen and L. Wos, Unit refutations and Horn sets, Journal of the ACM 21 (1974) 590-605.
H.A. Kautz and B. Selman, Forming concepts for fast inference, in: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI'92) (1992) pp. 786-793.
H.A. Kautz and B. Selman, An empirical evaluation of knowledge compilation by theory approximation, in: Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI'94) (1994) pp. 155-161.
H.R. Lewis, Renaming a set of clauses as a Horn set, Journal of the ACM 25 (1978) 134-135.
C.H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, MA, 1994).
R. Schrag, Compilation for critically constrained knowledge bases, in: Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI'96) (1996) pp. 510-515.
B. Selman and H.A. Kautz, Knowledge compilation using Horn approximations, in: Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI'91) (1991) pp. 904-909.
B. Selman and H.A. Kautz, Knowledge compilation and theory approximation, Journal of the ACM 43 (1996) 193-224.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Cadoli, M., Palopoli, L. & Scarcello, F. Propositional lower bounds: Algorithms and complexity. Annals of Mathematics and Artificial Intelligence 27, 129–148 (1999). https://doi.org/10.1023/A:1018971231561
Issue Date:
DOI: https://doi.org/10.1023/A:1018971231561