×

A subclass of Horn CNFs optimally compressible in polynomial time. (English) Zbl 1253.68311

Summary: The problem of Horn minimization (HM) can be stated as follows: given a Horn CNF representing a Boolean function \(f\), find a shortest possible (optimally compressed) CNF representation of \(f\), i.e., a CNF representation of \(f\) which consists of the minimum possible number of clauses. This problem is the formalization of the problem of knowledge compression for speeding up queries to propositional Horn expert systems, and it is known to be NP-hard. There are two subclasses of Horn functions for which HM is known to be solvable in polynomial time: acyclic and quasi-acyclic Horn functions. In this paper we define a new class of Horn functions properly containing both of the known classes and design a polynomial-time HM algorithm for this new class.

MSC:

68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
06E30 Boolean functions

Software:

Ltur
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ausiello, G., D’Atri, A., Sacca, D.: Minimal representation of directed hypergraphs. SIAM J. Comput. 15, 418–431 (1986) · Zbl 0602.68056 · doi:10.1137/0215029
[2] Boros, E., Čepek, O.: On the complexity of Horn minimization. RUTCOR Research Report RRR 1-94, Rutgers University, New Brunswick, NJ (1994)
[3] Boros, E., Čepek, O., Kogan, A.: Horn minimization by iterative decomposition. Ann. Math. Artif. Intell. 23, 321–343 (1998) · Zbl 0913.68192 · doi:10.1023/A:1018932728409
[4] Boros, E., Čepek, O., Kogan, A., Kučera, P.: Exclusive and essential sets of implicates of Boolean functions. Discrete Appl. Math. 158(2), 81–96 (2010) · Zbl 1194.06010 · doi:10.1016/j.dam.2009.08.012
[5] Buning, H.K., Letterman, T.: Propositional Logic: Deduction and Algorithms. Cambridge University Press (1999)
[6] Cadoli, M., Donini, F.M.: A survey on knowledge compilation. AI Commun. 10(3–4), 137–150 (1997)
[7] Čepek, O.: Structural properties and minimization of Horn Boolean functions. Doctoral dissertation, Rutgers University, New Brunswick, NJ (1995)
[8] Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229–264 (2002) · Zbl 1045.68131
[9] Dechter, R., Pearl, J.: Structure identification in relational data. Artif. Intell. 58, 237–270 (1992) · Zbl 0782.68095 · doi:10.1016/0004-3702(92)90009-M
[10] Delobel, C., Casey, R.G.: Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. Develop. 17, 374–386 (1973) · Zbl 0259.68016 · doi:10.1147/rd.175.0374
[11] Dowling, W.F., Gallier, J.H.: Linear time algorithms for testing the satisfiability of propositional Horn formulae. J. Log. Program. 3, 267–284 (1984) · Zbl 0593.68062 · doi:10.1016/0743-1066(84)90014-1
[12] Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM J. Comput. 5, 653–665 (1976) · Zbl 0346.05112 · doi:10.1137/0205044
[13] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (1979) · Zbl 0411.68039
[14] Genesereth, M.R., Nilsson, N.J.: Logical Foundations of Artificial Intelligence. Morgan Kaufmann, Los Altos, CA (1987) · Zbl 0645.68104
[15] Hammer, P.L., Kogan, A.: Horn functions and their DNFs. Inf. Process. Lett. 44, 23–29 (1992) · Zbl 0794.68148 · doi:10.1016/0020-0190(92)90250-Y
[16] Hammer, P.L., Kogan, A.: Horn function minimization and knowledge compression in production rule bases. RUTCOR Research Report RRR 8-92, Rutgers University, New Brunswick, NJ (1992)
[17] Hammer, P.L., Kogan, A.: Optimal compression of propositional Horn knowledge bases: complexity and approximation. Artif. Intell. 64, 131–145 (1993) · Zbl 0935.68105 · doi:10.1016/0004-3702(93)90062-G
[18] Hammer, P.L., Kogan, A.: Knowledge compression–logic minimization for expert systems. In: Computers As Our Better Partners. Proceedings of the IISF/ACM Japan International Symposium, pp. 306–312. World Scientific, Singapore (1994)
[19] Hammer, P.L., Kogan, A.: Quasi-acyclic propositional Horn knowledge bases: optimal compression. IEEE Trans. Knowl. Data Eng. 7(5), 751–762 (1995) · Zbl 05109665 · doi:10.1109/69.469822
[20] Ibaraki, T., Kogan, A., Makino, K.: Functional dependencies in Horn theories. Artif. Intell. 108(1–2), 1–30 (1999) · Zbl 0914.68185 · doi:10.1016/S0004-3702(98)00114-3
[21] Ibaraki, T., Kogan, A., Makino, K.: On functional dependencies in q-Horn theories. Artif. Intell. 131(1–2), 171–187 (2001) · Zbl 0996.68197 · doi:10.1016/S0004-3702(01)00118-7
[22] Itai, A., Makowsky, J.A.: Unification as a complexity measure for logic programming. J. Log. Program. 4, 105–117 (1987) · Zbl 0641.68143 · doi:10.1016/0743-1066(87)90014-8
[23] Kautz, H., Kearns, M., Selman, B.: Forming concepts for fast inference. In: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI’92), pp. 786–793. AAAI, San Jose, CA (1992)
[24] Maier, D.: Minimal covers in the relational database model. J. ACM 27, 664–674 (1980) · Zbl 0466.68085 · doi:10.1145/322217.322223
[25] Minoux, M.: LTUR: a simplified linear time unit resolution algorithm for Horn formulae and computer implementation. Inf. Process. Lett. 29, 1–12 (1988) · Zbl 0658.68110 · doi:10.1016/0020-0190(88)90124-X
[26] Quine, W.: The problem of simplifying the truth functions. Am. Math. Mon. 59, 521–531 (1952) · Zbl 0048.24503 · doi:10.2307/2308219
[27] Quine, W.: A way to simplify truth functions. Am. Math. Mon. 62, 627–631 (1955) · Zbl 0068.24209 · doi:10.2307/2307285
[28] Raghavan, S.: A note on Eswaran and Tarjan’s algorithm for the strong connectivity augmentation problem. In: Golden, B.L., Raghavan, S., Wasil, E.A. (eds.) The Next Wave in Computing, Optimization, and Decision Technologies, pp. 19–26. Springer (2005)
[29] Reiter, R., de Kleer, J.: Foundations of assumption-based truth maintenance systems: preliminary report. In: Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI’87), pp. 183–189. AAAI, San Jose, CA (1987)
[30] Selman, B., Kautz, H.: Knowledge compilation and theory approximation. J. ACM 43(2), 193–224 (1996) · Zbl 0882.68137 · doi:10.1145/226643.226644
[31] Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 2, 146–160 (1972) · Zbl 0251.05107 · doi:10.1137/0201010
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.