{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:50:38Z","timestamp":1744217438986,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540653851"},{"type":"electronic","value":"9783540493815"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49381-6_26","type":"book-chapter","created":{"date-parts":[[2007,12,3]],"date-time":"2007-12-03T06:47:50Z","timestamp":1196664470000},"page":"237-246","source":"Crossref","is-referenced-by-count":5,"title":["Generalized Graph Colorability and Compressibility of Boolean Formulae"],"prefix":"10.1007","author":[{"given":"Richard","family":"Nock","sequence":"first","affiliation":[]},{"given":"Pascal","family":"Jappy","sequence":"additional","affiliation":[]},{"given":"Jean","family":"Sallantin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,3,29]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"H. Aizenstein and L. Pitt. Exact learning of read-k-disjoint DNF and not-so-disjoint-DNF. In Proc. of the 5th International Conference on Computational Learning Theory, pages 71\u201376, 1992.","DOI":"10.1145\/130385.130393"},{"key":"26_CR2","first-page":"183","volume":"19","author":"H. Aizenstein","year":"1995","unstructured":"H. Aizenstein and L. Pitt. On the learnability of Disjunctive Normal Form formulas. Machine Learning, 19:183\u2013208, 1995.","journal-title":"Machine Learning"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"J. L. Balcazar, J. Diaz, and J. Gabarro. Structural Complexity I. Springer Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"U. Berggren. Linear time deterministic learning of k-term-DNF. In Proc. of the 6th International Conference on Computational Learning Theory, pages 37\u201340, 1993.","DOI":"10.1145\/168304.168309"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, R. Khardon, E. Kushilevitz, L. Pitt, and D. Roth. On learning read-k-satisfy-j DNF. In Proc. of the 7International Conference on Computational Learning Theory, pages 110\u2013117, 1994.","DOI":"10.1145\/180139.181051"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam\u2019s razor. Information Processing Letters, pages 377\u2013380, 1987.","DOI":"10.1016\/0020-0190(87)90114-1"},{"key":"26_CR7","unstructured":"C. Brunk and M. Pazzani. Noise-tolerant relational concept learning. In Proc. of the 8th International Conference on Machine Learning, 1991."},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, Z. Chen, S. E. Decatur, and S. Homer. On the learnability of zn-DNF formulas. In Proc. of the 8th International Conference on Computational Learning Theory, pages 198\u2013205, 1995.","DOI":"10.1145\/225298.225322"},{"key":"26_CR9","unstructured":"W. W. Cohen. PAC-learning a restricted class of recursive logic programs. In Proc. of AAAI-93, pages 86\u201392, 1993."},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"W. W. Cohen. Fast effective rule induction. In Proc. of the 12th International Conference on Machine Learning, pages 115\u2013123, 1995.","DOI":"10.1016\/B978-1-55860-377-6.50023-2"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"C. de la Higuera. Characteristic sets for polynomial grammatical inference. Machine Learning, pages 1\u201314, 1997.","DOI":"10.1007\/BFb0033342"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"L. de Raedt. Iterative concept learning and construction by analogy. Machine Learning, pages 107\u2013150, 1992.","DOI":"10.1007\/BF00992861"},{"key":"26_CR13","unstructured":"U. Feige and J. Kilian. Zero knowledge and the chromatic number. draft, 1996."},{"key":"26_CR14","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability, a guide to the theory of NP-Completeness. Bell Telephone Laboratories, 1979."},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"S. A. Goldman and H. D. Mathias. Learning k-term-DNF formulas with an incomplete membership oracle. In Proc. of the 5th International Conference on Computational Learning Theory, pages 77\u201384, 1992.","DOI":"10.1145\/130385.130394"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"J. Hastad. Clique is hard to approximate within n1-\u03b5. In FOCS\u201996, pages 627\u2013636, 1996.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"R.C. Holte. Very simple classification rules perform well on most commonly used datasets. Machine Learning, pages 63\u201391, 1993.","DOI":"10.1023\/A:1022631118932"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"M. J. Kearns and U. V. Vazirani. An Introduction to Computational Learning Theory. M.I.T. Press, 1994.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"M.J. Kearns, M. Li, L. Pitt, and L. Valiant. On the learnability of boolean formulae. Proceedings of the Nineteenth Annual A.C.M. Symposium on Theory of Computing, pages 285\u2013295, 1987.","DOI":"10.1145\/28395.28426"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"R. Khardon. On using the fourier transform to learn disjoint DNF. Information Processing Letters, pages 219\u2013222, 1994.","DOI":"10.1016\/0020-0190(94)90057-4"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"N. Lavrac, S. Dzeroski, and M. Grobelnik. Learning non-recursive definitions of relations with linus. In European Working Session in Learning, 1991.","DOI":"10.1007\/BFb0017020"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"K. Lund and M. Yannakakis. On the hardness of approximating minimization problems. In Proc. of the 25th Symposium on the Theory of Computing, pages 286\u2013293, 1993.","DOI":"10.1145\/167088.167172"},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"Y. Mansour. An O(nlog log n) algorithm for dnf under the uniform distribution. In Proc. of the 5th International Conference on Computational Learning Theory, pages 53\u201361, 1992.","DOI":"10.1145\/130385.130391"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"S. Muggleton and C. Feng. Efficient induction of logic programs. In Inductive Logic Programming, 1994.","DOI":"10.1145\/180139.178095"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"R. Nock and O. Gascuel. On learning decision committees. In Proc. of the 12th International Conference on Machine Learning, pages 413\u2013420, 1995.","DOI":"10.1016\/B978-1-55860-377-6.50058-X"},{"key":"26_CR26","doi-asserted-by":"crossref","unstructured":"J. Pagallo and D. Haussler. Boolean feature discovery in empirical learning. Machine Learning, 1990.","DOI":"10.1023\/A:1022611825350"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"K. Pillaipakkamnatt and V. Raghavan. On the limits of proper learnability of subclasses of DNF formulae. In Proc. of the 7th International Conference on Computational Learning Theory, pages 118\u2013129, 1994.","DOI":"10.1145\/180139.181063"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"L. Pitt and L. G. Valiant. Computational limitations on learning from examples. J. ACM, pages 965\u2013984, 1988.","DOI":"10.1145\/48014.63140"},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"J. R. Quinlan. Learning logical definition from relations. Machine Learning, pages 239\u2013270, 1990.","DOI":"10.1007\/BF00117105"},{"key":"26_CR30","unstructured":"J. R. Quinlan. C4.5: programs for machine learning. Morgan Kaufmann, 1994."},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"J. R. Quinlan. MDL and categorical theories (continued). In Proc. of the 12th International Conference on Machine Learning, pages 464\u2013470, 1995.","DOI":"10.1016\/B978-1-55860-377-6.50064-5"},{"key":"26_CR32","unstructured":"C. Rouveirol. ITOU: induction of first-order theories. Inductive Logic Programming, 1992."},{"key":"26_CR33","unstructured":"S. B. Thrun, J. Bala, E. Bloedorn, I. Bratko, B. Cestnik, J. Cheng, K. De Jong, S. Dzeroski, S. E. Fahlman, D. Fisher, R. Hamann, K. Kaufman, S. Keller, I. Kononenko, J. Kreuziger, R. S. Michalski, T. Mitchell, P. Pachowicz, Y. Reich, H. Vafaie, W. Van de Welde, W. Wenzel, J. Wnek, and J. Zhang. The MONK\u2019s problems: a performance comparison of different lear ning algorithms. Technical Report CMU-CS-91-197, Carnegie Mellon University, 1991."},{"key":"26_CR34","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. A theory of the learnable. Communications of the ACM, pages 1134\u20131142, 1984.","DOI":"10.1145\/1968.1972"},{"key":"26_CR35","unstructured":"L. G. Valiant. Learning disjunctions of conjunctions. In Proc. of the 9th IJCAI, pages 560\u2013566, 1985."},{"key":"26_CR36","unstructured":"J Wnek and R. Michalski. Hypothesis-driven constructive induction in AQ17. In Proc. of the 12th IJCAI, 1991."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49381-6_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T04:58:41Z","timestamp":1737608321000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49381-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540653851","9783540493815"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-49381-6_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}