{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:37:20Z","timestamp":1758274640918,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_38","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"438-450","source":"Crossref","is-referenced-by-count":5,"title":["On Approximate Horn Formula Minimization"],"prefix":"10.1007","author":[{"given":"Amitava","family":"Bhattacharya","sequence":"first","affiliation":[]},{"given":"Bhaskar","family":"DasGupta","sequence":"additional","affiliation":[]},{"given":"Dhruv","family":"Mubayi","sequence":"additional","affiliation":[]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"38_CR1","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s00453-007-9055-0","volume":"51","author":"R. Albert","year":"2008","unstructured":"Albert, R., DasGupta, B., Dondi, R., Sontag, E.: Inferring (biological) signal transduction networks via transitive reductions of directed graphs. Algorithmica\u00a051(2), 129\u2013159 (2008)","journal-title":"Algorithmica"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jagm.1994.1005","volume":"16","author":"N. Alon","year":"1994","unstructured":"Alon, N., Duke, R.A., Lefmann, H., R\u00f6dl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. J. of Algorithms\u00a016, 80\u2013109 (1994)","journal-title":"J. of Algorithms"},{"key":"38_CR3","first-page":"147","volume":"9","author":"D. Angluin","year":"1992","unstructured":"Angluin, D., Frazier, M., Pitt, L.: Learning conjunctions of Horn clauses. Machine Learning\u00a09, 147\u2013164 (1992)","journal-title":"Machine Learning"},{"issue":"2","key":"38_CR4","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0215029","volume":"15","author":"G. Ausiello","year":"1986","unstructured":"Ausiello, G., D\u2019atri, A., Sacc\u00e0, D.: Minimal representations of directed hypergraphs. SIAM J. Comput.\u00a015(2), 418\u2013431 (1986)","journal-title":"SIAM J. Comput."},{"key":"38_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-03367-4_7","volume-title":"11th Algorithms and Data Structures Symposium","author":"P. Berman","year":"2009","unstructured":"Berman, P., DasGupta, B., Karpinski, M.: Approximating transitive reduction problems for directed networks. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f2th, C.D. (eds.) 11th Algorithms and Data Structures Symposium. LNCS, vol.\u00a05664, pp. 74\u201385. Springer, Heidelberg (2009)"},{"key":"38_CR6","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity, Report TR03-049 (2003)"},{"key":"38_CR7","volume-title":"Boolean Functions: Theory, Algorithms and Applications","author":"E. Boros","year":"2010","unstructured":"Boros, E.: Horn functions. In: Crama, Y., Hammer, P.L. (eds.) Boolean Functions: Theory, Algorithms and Applications, Cambridge Univ. Press, Cambridge (forthcoming, 2010)"},{"key":"38_CR8","unstructured":"Boros, E., \u010cepek, O.: On the complexity of Horn minimization, Rutcor Research Report 1-94 (1994)"},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF01531068","volume":"1","author":"E. Boros","year":"1990","unstructured":"Boros, E., Crama, Y., Hammer, P.L.: Polynomial-time inference of all valid implications for Horn and related formulae. Ann. Math. Artif. Intell.\u00a01, 21\u201332 (1990)","journal-title":"Ann. Math. Artif. Intell."},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/BF00264314","volume":"23","author":"S. Bublitz","year":"1996","unstructured":"Bublitz, S.: Decomposition of graphs and monotone formula size of homogeneous fuctions. Acta Informatica\u00a023, 689\u2013696 (1996)","journal-title":"Acta Informatica"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0166-218X(02)00209-3","volume":"127","author":"N. Caspard","year":"2003","unstructured":"Caspard, N., Monjardet, B.: The lattice of closure systems, closure operators and implications on a finite set: a survey. Discrete Appl. Math.\u00a0127, 241\u2013269 (2003)","journal-title":"Discrete Appl. Math."},{"key":"38_CR12","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/0012-365X(78)90168-1","volume":"24","author":"A.K. Chandra","year":"1978","unstructured":"Chandra, A.K., Markowsky, G.: On the number of prime implicants. Discrete Math.\u00a024, 7\u201311 (1978)","journal-title":"Discrete Math."},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Chung, F.R.K., Erd\u0151s, P., Spencer, J.: On the decomposition of graphs into complete bipartite graphs. Studies in Pure Mathematics, To the Memory of Paul Tur\u00e1n, pp. 95-101. Akad\u00e9miai Kiad\u00f3 (1983)","DOI":"10.1007\/978-3-0348-5438-2_10"},{"key":"38_CR14","volume-title":"Boolean Functions and Models of Computation","author":"P. Clote","year":"2003","unstructured":"Clote, P., Kranakis, E.: Boolean Functions and Models of Computation. Springer, Heidelberg (2003)"},{"key":"38_CR15","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: Feasibly constructive proofs and the propositional calculus. In: STOC, pp. 83\u201397 (1975)","DOI":"10.1145\/800116.803756"},{"key":"38_CR16","unstructured":"Feige, U., Kogan, S.: Hardness of approximation of the balanced complete bipartite subgraph problem, Tech. Rep. MCS04-04, Dept. of Comp. Sci. and Appl. Math., The Weizmann Inst. of Science (2004)"},{"key":"38_CR17","first-page":"327","volume":"27","author":"A. Fl\u00f6gel","year":"1993","unstructured":"Fl\u00f6gel, A., Kleine B\u00fcning, H., Lettmann, T.: On the restricted equivalence subclasses of propositional logic. ITA\u00a027, 327\u2013340 (1993)","journal-title":"ITA"},{"key":"38_CR18","unstructured":"Frazier, M.D.: Matters Horn and other features in the computational learning theory landscape: the notion of membership, Ph.D. thesis, Univ. of Illinois at Urbana-Champaign (1994)"},{"key":"38_CR19","first-page":"5","volume":"95","author":"J.L. Guigues","year":"1986","unstructured":"Guigues, J.L., Duquenne, V.: Familles minimales d\u2019implications informatives r\u00e9sultant d\u2019un tableau de donn\u00e9es binaires. Math. Sci. Humaines\u00a095, 5\u201318 (1986)","journal-title":"Math. Sci. Humaines"},{"key":"38_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0020-0190(92)90250-Y","volume":"44","author":"P.L. Hammer","year":"1992","unstructured":"Hammer, P.L., Kogan, A.: Horn functions and their DNFs. Information Processing Letters\u00a044, 23\u201329 (1992)","journal-title":"Information Processing Letters"},{"key":"38_CR21","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0004-3702(93)90062-G","volume":"64","author":"P.L. Hammer","year":"1993","unstructured":"Hammer, P.L., Kogan, A.: Optimal compression of propositional Horn knowledge bases: complexity and approximation. Artificial Intelligence\u00a064, 131\u2013145 (1993)","journal-title":"Artificial Intelligence"},{"key":"38_CR22","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1109\/69.469822","volume":"7","author":"P.L. Hammer","year":"1995","unstructured":"Hammer, P.L., Kogan, A.: Quasi-acyclic Horn knowledge bases: optimal compression. IEEE Trans. on Knowledge and Data Engineering\u00a07, 751\u2013762 (1995)","journal-title":"IEEE Trans. on Knowledge and Data Engineering"},{"key":"38_CR23","volume-title":"The Steiner Tree Problem","author":"F.K. Hwang","year":"1992","unstructured":"Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. North-Holland, Amsterdam (1992)"},{"key":"38_CR24","unstructured":"Kirchner, S.: Lower bounds for Steiner tree algorithms and the construction of bicliques in dense graphs, Ph.D. Dissertation, Humboldt-Universit\u00e4t zu Berlin (2008) (in German)"},{"key":"38_CR25","volume-title":"Propositional Logic: Deduction and Algorithms","author":"H. Kleine B\u00fcning","year":"1999","unstructured":"Kleine B\u00fcning, H., Lettmann, T.: Propositional Logic: Deduction and Algorithms. Cambridge Univ. Press, Cambridge (1999)"},{"issue":"3","key":"38_CR26","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/S0097539702416736","volume":"33","author":"G. Kortsarz","year":"2004","unstructured":"Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximating vertex-connectivity network design problems. SIAM J. Comput.\u00a033(3), 704\u2013720 (2004)","journal-title":"SIAM J. Comput."},{"key":"38_CR27","doi-asserted-by":"crossref","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"T. K\u0151v\u00e1ri","year":"1954","unstructured":"K\u0151v\u00e1ri, T., S\u00f3s, V.T., Tur\u00e1n, P.: On a problem of K. Zarankiewicz. Colloq. Math.\u00a03, 50\u201357 (1954)","journal-title":"Colloq. Math."},{"key":"38_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/SAT190072","volume":"7","author":"M. Langlois","year":"2009","unstructured":"Langlois, M., Sloan, R.H., Tur\u00e1n, G.: Horn upper bounds and renaming. J. Satisfiability, Boolean Modelling and Computation\u00a07, 1\u201315 (2009)","journal-title":"J. Satisfiability, Boolean Modelling and Computation"},{"key":"38_CR29","first-page":"466","volume-title":"Horn complements: towards Horn-to-Horn belief revision","author":"M. Langlois","year":"2008","unstructured":"Langlois, M., Sloan, R.H., Sz\u00f6r\u00e9nyi, B., Tur\u00e1n, G.: Horn complements: towards Horn-to-Horn belief revision, pp. 466\u2013471. AAAI, Menlo Park (2008)"},{"key":"38_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-642-02029-2_6","volume-title":"Graph Theory, Computational Intelligence and Thought","author":"M. Langlois","year":"2009","unstructured":"Langlois, M., Mubayi, D., Sloan, R.H., Tur\u00e1n, G.: Combinatorial Problems for Horn Clauses. In: Lipshteyn, M., Levit, V.E., McConnell, R.M. (eds.) Graph Theory, Computational Intelligence and Thought. LNCS, vol.\u00a05420, pp. 54\u201365. Springer, Heidelberg (2009)"},{"key":"38_CR31","unstructured":"Lov\u00e1sz, L.: Coverings and colorings of hypergraphs. In: Proc. 4th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Math., pp. 3\u201312 (1973)"},{"key":"38_CR32","volume-title":"The Theory of Relational Databases","author":"D. Maier","year":"1983","unstructured":"Maier, D.: The Theory of Relational Databases. Comp. Sci. Press, Rockville (1983)"},{"key":"38_CR33","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.ipl.2009.11.015","volume":"110","author":"D. Mubayi","year":"2010","unstructured":"Mubayi, D., Tur\u00e1n, G.: Finding bipartite subgraphs efficiently. Inf. Proc. Lett.\u00a0110, 174\u2013177 (2010)","journal-title":"Inf. Proc. Lett."},{"key":"38_CR34","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","volume":"80","author":"J. Orlin","year":"1977","unstructured":"Orlin, J.: Contentment in graph theory: covering graphs with cliques. Indag. Math.\u00a080, 406\u2013424 (1977)","journal-title":"Indag. Math."},{"key":"38_CR35","volume-title":"Artificial Intelligence: A Modern Approach","author":"S. Russell","year":"2002","unstructured":"Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 2nd edn. Prentice Hall, Englewood Cliffs (2002)","edition":"2"},{"key":"38_CR36","doi-asserted-by":"crossref","unstructured":"Singh, P., Lin, T., Mueller, E.T., Lim, G., Perkins, T., Zhu, W.L.: Open Mind Common Sense: knowledge acquisition from the general public., CoopIS\/DOA\/ODBASE, 1223\u20131237 (2002)","DOI":"10.1007\/3-540-36124-3_77"},{"key":"38_CR37","first-page":"203","volume":"10","author":"T. Tarj\u00e1n","year":"1975","unstructured":"Tarj\u00e1n, T.: Complexity of lattice-configurations. Studia Sci. Math. Hung.\u00a010, 203\u2013211 (1975)","journal-title":"Studia Sci. Math. Hung."},{"key":"38_CR38","unstructured":"Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Seminars in Mathematics, V. A. Steklov Mathematical Institut, Leningrad, vol.\u00a08 (1968)"},{"key":"38_CR39","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02579163","volume":"4","author":"Z. Tuza","year":"1984","unstructured":"Tuza, Z.: Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices. Combinatorica\u00a04, 111\u2013116 (1984)","journal-title":"Combinatorica"},{"key":"38_CR40","doi-asserted-by":"crossref","unstructured":"Umans, C.: Hardness of approximating $\\Sigma_2^p$ minimization problems. In: FOCS, pp. 465-474 (1999)","DOI":"10.1109\/SFFCS.1999.814619"},{"key":"38_CR41","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1006\/jcss.2001.1775","volume":"63","author":"C. Umans","year":"2001","unstructured":"Umans, C.: The Minimum Equivalent DNF problem and shortest implicants. J. Comput. Syst. Sci.\u00a063, 597\u2013611 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"38_CR42","unstructured":"Vetta, A.: Approximating the minimum strongly connected subgraph via a matching lower bound. In: 12th ACM-SIAM Symposium on Discrete Algorithms, pp. 417\u2013426 (2001)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:31:35Z","timestamp":1740241895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}