Semantical and computational aspects of Horn approximations. (English) Zbl 0945.68160
Summary: Selman and Kautz proposed a method, called Horn approximation, for speeding up inference in propositional Knowledge Bases. Their technique is based on the compilation of a propositional formula into a pair of Horn formulae: a Horn Greatest Lower Bound (GLB) and a Horn Least Upper Bound (LUB). In this paper we focus on GLBs and address two questions that have been only marginally addressed so far: We obtain semantical as well as computational results. The major semantical result is: The set of minimal models of a propositional formula and the set of minimum models of its Horn GLBs are the same. The major computational result is: Finding a Horn GLB of a propositional formula in CNF is NP-equivalent.
MSC:
| 68T30 | Knowledge representation |
References:
| [1] | Ben-Eliyahu, R.; Dechter, R., On computing minimal models, Ann. Math. Artificial Intelligence, 3-27 (1996) · Zbl 0891.68109 |
| [2] | Boufkhad, Y., Algorithms for propositional KB approximation, (Proc. AAAI-98, Madison, WI (1998)), 280-285 |
| [3] | Cadoli, M., On the complexity of model finding for nonmonotonic propositional logics, (Marchetti Spaccamela, A.; Mentrasti, P.; Venturini Zilli, M., Proc. 4th Italian Conference on Theoretical Computer Science (1992), World Scientific: World Scientific Singapore), 125-139 |
| [4] | Cadoli, M., Semantical and computational aspects of Horn approximations, (Proc. IJCAI-93, Chambéry, France (1993)), 39-44 · Zbl 0945.68160 |
| [5] | Cadoli, M.; Donini, F. M., A survey on knowledge compilation, AI Communications—The European Journal on Artificial Intelligence, Vol. 10, 137-150 (1997) |
| [6] | Chen, Z.; Toda, S., The complexity of selecting maximal solutions, Inform. and Comput., Vol. 119, 231-239 (1995) · Zbl 0834.68045 |
| [7] | del Val, A., An analysis of approximate knowledge compilation, (Proc. IJCAI-95, Montreal, Quebec (1995)), 830-836 |
| [8] | Dowling, W. P.; Gallier, J. H., Linear-time algorithms for testing the satisfiability of propositional Horn formulae, J. Logic Programming, Vol. 1, 267-284 (1984) · Zbl 0593.68062 |
| [9] | Eiter, T.; Gottlob, G., Propositional circumscription and extended closed world reasoning are \(Π^p2\) -complete, Theoret. Comput. Sci., Vol. 114, 231-245 (1993) · Zbl 0786.68085 |
| [10] | Eiter, T.; Ibaraki, T.; Makino, K., Disjunctions of Horn theories and their cores, (Proc. 9th Annual Symposium on Algorithms and Computation (ISAAC-98) (1998)), 49-58 · Zbl 0923.03055 |
| [11] | Gelernter, H., Realization of a geometry theorem-proving machine, (Proc. International Conference on Information Processing (1959), UNESCO House: UNESCO House Paris), 273-282 · Zbl 0114.06901 |
| [12] | Gogic, G.; Papadimitriou, C.; Sideri, M., Incremental recompilation of knowledge, J. Artificial Intelligence Res., Vol. 8, 23-37 (1998) · Zbl 0895.68133 |
| [13] | Greiner, R.; Schuurmans, D., Learning useful Horn approximations, (Proc. Third International Conference on the Principles of Knowledge Representation and Reasoning (KR-92), Cambridge, MA (1992)), 383-392 |
| [14] | Kautz, H. A.; Kearns, M. J.; Selman, B., Horn approximations of empirical data, Artificial Intelligence, Vol. 74, 129-145 (1995) · Zbl 1014.03514 |
| [15] | Kautz, H. A.; Selman, B., Forming concepts for fast inference, (Proc. AAAI-92, San Jose, CA (1992)), 786-793 |
| [16] | Kautz, H. A.; Selman, B., An empirical evaluation of knowledge compilation by theory approximation, (Proc. AAAI-94, Seattle, WA (1994)), 155-161 |
| [17] | Kavvadias, D.; Papadimitriou, C. H.; Sideri, M., On Horn envelopes and hypergraph transversals, (Proc. 4th Annual Symposium on Algorithms and Computation (ISAAC-93) (1993)), 399-405 · Zbl 0925.03036 |
| [18] | Khardon, R.; Roth, D., Reasoning with models, Artificial Intelligence, Vol. 87, 187-213 (1996) · Zbl 1506.68149 |
| [19] | Lifschitz, V., Computing circumscription, (Proc. IJCAI-85, Los Angeles, CA (1985)), 121-127 |
| [20] | McCarthy, J., Circumscription—A form of non-monotonic reasoning, Artificial Intelligence, Vol. 13, 27-39 (1980) · Zbl 0435.68073 |
| [21] | Papadimitriou, C. H., Computational Complexity (1994), Addison Wesley: Addison Wesley Reading, MA · Zbl 0557.68033 |
| [22] | Roth, D., On the hardness of approximate reasoning, (Proc. IJCAI-93, Chambéry, France (1993)), 613-618 |
| [23] | Selman, B.; Kautz, H. A., Knowledge compilation using Horn approximations, (Proc. AAAI-91, Anaheim, CA (1991)), 904-909 |
| [24] | Selman, B.; Kautz, H. A., Knowledge compilation and theory approximation, J. ACM, Vol. 43, 193-224 (1996) · Zbl 0882.68137 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
