{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:33Z","timestamp":1759638333839},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2009,12]]},"DOI":"10.1007\/s10472-010-9197-7","type":"journal-article","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T07:10:42Z","timestamp":1277449842000},"page":"249-291","source":"Crossref","is-referenced-by-count":10,"title":["A subclass of Horn CNFs optimally compressible in polynomial time"],"prefix":"10.1007","volume":"57","author":[{"given":"Endre","family":"Boros","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ond\u0159ej","family":"\u010cepek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Kogan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr","family":"Ku\u010dera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,6,26]]},"reference":[{"key":"9197_CR1","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0215029","volume":"15","author":"G Ausiello","year":"1986","unstructured":"Ausiello, G., D\u2019Atri, A., Sacca, D.: Minimal representation of directed hypergraphs. SIAM J. Comput. 15, 418\u2013431 (1986)","journal-title":"SIAM J. Comput."},{"key":"9197_CR2","unstructured":"Boros, E., \u010cepek, O.: On the complexity of Horn minimization. RUTCOR Research Report RRR 1-94, Rutgers University, New Brunswick, NJ (1994)"},{"key":"9197_CR3","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1023\/A:1018932728409","volume":"23","author":"E Boros","year":"1998","unstructured":"Boros, E., \u010cepek, O., Kogan, A.: Horn minimization by iterative decomposition. Ann. Math. Artif. Intell. 23, 321\u2013343 (1998)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"2","key":"9197_CR4","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.dam.2009.08.012","volume":"158","author":"E Boros","year":"2010","unstructured":"Boros, E., \u010cepek, O., Kogan, A., Ku\u010dera, P.: Exclusive and essential sets of implicates of Boolean functions. Discrete Appl. Math. 158(2), 81\u201396 (2010)","journal-title":"Discrete Appl. Math."},{"key":"9197_CR5","unstructured":"Buning, H.K., Letterman, T.: Propositional Logic: Deduction and Algorithms. Cambridge University Press (1999)"},{"issue":"3\u20134","key":"9197_CR6","first-page":"137","volume":"10","author":"M Cadoli","year":"1997","unstructured":"Cadoli, M., Donini, F.M.: A survey on knowledge compilation. AI Commun. 10(3\u20134), 137\u2013150 (1997)","journal-title":"AI Commun."},{"key":"9197_CR7","unstructured":"\u010cepek, O.: Structural properties and minimization of Horn Boolean functions. Doctoral dissertation, Rutgers University, New Brunswick, NJ (1995)"},{"key":"9197_CR8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229\u2013264 (2002)","journal-title":"J. Artif. Intell. Res."},{"key":"9197_CR9","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0004-3702(92)90009-M","volume":"58","author":"R Dechter","year":"1992","unstructured":"Dechter, R., Pearl, J.: Structure identification in relational data. Artif. Intell. 58, 237\u2013270 (1992)","journal-title":"Artif. Intell."},{"key":"9197_CR10","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1147\/rd.175.0374","volume":"17","author":"C Delobel","year":"1973","unstructured":"Delobel, C., Casey, R.G.: Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. Develop. 17, 374\u2013386 (1973)","journal-title":"IBM J. Res. Develop."},{"key":"9197_CR11","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"3","author":"WF Dowling","year":"1984","unstructured":"Dowling, W.F., Gallier, J.H.: Linear time algorithms for testing the satisfiability of propositional Horn formulae. J. Log. Program. 3, 267\u2013284 (1984)","journal-title":"J. Log. Program."},{"key":"9197_CR12","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"KP Eswaran","year":"1976","unstructured":"Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM J. Comput. 5, 653\u2013665 (1976)","journal-title":"SIAM J. Comput."},{"key":"9197_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"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)"},{"key":"9197_CR14","volume-title":"Logical Foundations of Artificial Intelligence","author":"MR Genesereth","year":"1987","unstructured":"Genesereth, M.R., Nilsson, N.J.: Logical Foundations of Artificial Intelligence. Morgan Kaufmann, Los Altos, CA (1987)"},{"key":"9197_CR15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0020-0190(92)90250-Y","volume":"44","author":"PL Hammer","year":"1992","unstructured":"Hammer, P.L., Kogan, A.: Horn functions and their DNFs. Inf. Process. Lett. 44, 23\u201329 (1992)","journal-title":"Inf. Process. Lett."},{"key":"9197_CR16","unstructured":"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)"},{"key":"9197_CR17","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0004-3702(93)90062-G","volume":"64","author":"PL Hammer","year":"1993","unstructured":"Hammer, P.L., Kogan, A.: Optimal compression of propositional Horn knowledge bases: complexity and approximation. Artif. Intell. 64, 131\u2013145 (1993)","journal-title":"Artif. Intell."},{"key":"9197_CR18","first-page":"306","volume-title":"Computers As Our Better Partners. Proceedings of the IISF\/ACM Japan International Symposium","author":"PL Hammer","year":"1994","unstructured":"Hammer, P.L., Kogan, A.: Knowledge compression\u2014logic minimization for expert systems. In: Computers As Our Better Partners. Proceedings of the IISF\/ACM Japan International Symposium, pp. 306\u2013312. World Scientific, Singapore (1994)"},{"issue":"5","key":"9197_CR19","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1109\/69.469822","volume":"7","author":"PL Hammer","year":"1995","unstructured":"Hammer, P.L., Kogan, A.: Quasi-acyclic propositional Horn knowledge bases: optimal compression. IEEE Trans. Knowl. Data Eng. 7(5), 751\u2013762 (1995)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1\u20132","key":"9197_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0004-3702(98)00114-3","volume":"108","author":"T Ibaraki","year":"1999","unstructured":"Ibaraki, T., Kogan, A., Makino, K.: Functional dependencies in Horn theories. Artif. Intell. 108(1\u20132), 1\u201330 (1999)","journal-title":"Artif. Intell."},{"issue":"1\u20132","key":"9197_CR21","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/S0004-3702(01)00118-7","volume":"131","author":"T Ibaraki","year":"2001","unstructured":"Ibaraki, T., Kogan, A., Makino, K.: On functional dependencies in q-Horn theories. Artif. Intell. 131(1\u20132), 171\u2013187 (2001)","journal-title":"Artif. Intell."},{"key":"9197_CR22","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0743-1066(87)90014-8","volume":"4","author":"A Itai","year":"1987","unstructured":"Itai, A., Makowsky, J.A.: Unification as a complexity measure for logic programming. J. Log. Program. 4, 105\u2013117 (1987)","journal-title":"J. Log. Program."},{"key":"9197_CR23","unstructured":"Kautz, H., Kearns, M., Selman, B.: Forming concepts for fast inference. In: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI\u201992), pp. 786\u2013793. AAAI, San Jose, CA (1992)"},{"key":"9197_CR24","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322217.322223","volume":"27","author":"D Maier","year":"1980","unstructured":"Maier, D.: Minimal covers in the relational database model. J. ACM 27, 664\u2013674 (1980)","journal-title":"J. ACM"},{"key":"9197_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(88)90124-X","volume":"29","author":"M Minoux","year":"1988","unstructured":"Minoux, M.: LTUR: a simplified linear time unit resolution algorithm for Horn formulae and computer implementation. Inf. Process. Lett. 29, 1\u201312 (1988)","journal-title":"Inf. Process. Lett."},{"key":"9197_CR26","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1080\/00029890.1952.11988183","volume":"59","author":"W Quine","year":"1952","unstructured":"Quine, W.: The problem of simplifying the truth functions. Am. Math. Mon. 59, 521\u2013531 (1952)","journal-title":"Am. Math. Mon."},{"key":"9197_CR27","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1080\/00029890.1955.11988710","volume":"62","author":"W Quine","year":"1955","unstructured":"Quine, W.: A way to simplify truth functions. Am. Math. Mon. 62, 627\u2013631 (1955)","journal-title":"Am. Math. Mon."},{"key":"9197_CR28","doi-asserted-by":"crossref","unstructured":"Raghavan, S.: A note on Eswaran and Tarjan\u2019s 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\u201326. Springer (2005)","DOI":"10.1007\/0-387-23529-9_2"},{"key":"9197_CR29","unstructured":"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\u201987), pp. 183\u2013189. AAAI, San Jose, CA (1987)"},{"issue":"2","key":"9197_CR30","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1145\/226643.226644","volume":"43","author":"B Selman","year":"1996","unstructured":"Selman, B., Kautz, H.: Knowledge compilation and theory approximation. J. ACM 43(2), 193\u2013224 (1996)","journal-title":"J. ACM"},{"key":"9197_CR31","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"2","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 2, 146\u2013160 (1972)","journal-title":"SIAM J. Comput."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-010-9197-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-010-9197-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-010-9197-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:58:14Z","timestamp":1559152694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-010-9197-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":31,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["9197"],"URL":"https:\/\/doi.org\/10.1007\/s10472-010-9197-7","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}