{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:13Z","timestamp":1725551113214},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_30","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T21:12:04Z","timestamp":1269897124000},"page":"331-342","source":"Crossref","is-referenced-by-count":6,"title":["Algebraic Characterizations of Small Classes of Boolean Functions"],"prefix":"10.1007","author":[{"given":"Ricard","family":"Gavald\u00e0","sequence":"first","affiliation":[]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"D. Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75:87\u2013106, 1987.","journal-title":"Information and Computation"},{"key":"30_CR2","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin. Queries and concept learning. Machine Learning, 2:319\u2013342, 1988.","journal-title":"Machine Learning"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"D.A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences, 38:150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(92)90237-P","volume":"42","author":"A.L. Blum","year":"1992","unstructured":"A.L. Blum. Rank-r decision trees are a subclass of r-decision lists. Information Processing Letters, 42:183\u2013185, 1992.","journal-title":"Information Processing Letters"},{"issue":"3","key":"30_CR5","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1145\/146637.146661","volume":"39","author":"M. Beaudry","year":"1992","unstructured":"M. Beaudry, P. McKenzie, and D. Th\u00e9rien. The membership problem in aperiodic transformation monoids. Journal of the ACM, 39(3):599\u2013616, 1992.","journal-title":"Journal of the ACM"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.1995.1075","volume":"51","author":"A. Blum","year":"1995","unstructured":"A. Blum and S. Rudich. Fast learning of k-term dnf formulas with queries. Journal of Computer and System Sciences, 51:367\u2013373, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/inco.1995.1164","volume":"123","author":"N.H. Bshouty","year":"1995","unstructured":"N.H. Bshouty. Exact learning boolean functions via the monotone theory. Information and Computation, 123:146\u2013153, 1995.","journal-title":"Information and Computation"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0890-5401(90)90007-5","volume":"89","author":"D.A. M. Barrington","year":"1990","unstructured":"D.A. Mix Barrington, H. Straubing, and D. Th\u00e9rien. Non-uniform automata over groups. Information and Computation, 89:109\u2013132, 1990.","journal-title":"Information and Computation"},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D.A. M. Barrington","year":"1988","unstructured":"D.A. Mix Barrington and D. Th\u00e9rien. Finite monoids and the fine structure of NC1. Journal of the ACM, 35:941\u2013952, 1988.","journal-title":"Journal of the ACM"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"J. Castro and J.L. Balc\u00e1zar. Simple PAC learning of simple decision lists. In Algorithmic Learning Theory, 6th International Workshop, ALT\u2019 95, Proceedings, volume 997, pages 239\u2013248. Springer, 1995.","DOI":"10.1007\/3-540-60454-5_42"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0890-5401(89)90001-1","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"A. Ehrenfeucht and D. Haussler. Learning decision trees from random examples. Information and Computation, 82:231\u2013246, 1989.","journal-title":"Information and Computation"},{"key":"30_CR12","unstructured":"S. Eilenberg. Automata, Languages, and Machines, volume B. Academic Press, 1976."},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"T. Elomaa. The biases of decision tree pruning strategies. In Advances in Intelligent Data Analysis: Proc. 3rd Intl. Symp., pages 63\u201374, 1999.","DOI":"10.1007\/3-540-48412-4_6"},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"R. Gavald\u00e0, D. Th\u00e9rien, and P. Tesson. Learning expressions and programs over monoids. In Technical Report R01-38, Department LSI, UPC, pages-, 2001.","DOI":"10.1007\/3-540-44693-1_25"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"53","author":"J.C. Jackson","year":"1997","unstructured":"J.C. Jackson. An efficient membership-query algorithm for learning dnf. Journal of Computer and System Sciences, 53:414\u2013440, 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"M.J. Kearns and U.V. Vazirani. An Introduction to Computational Learning Theory. The MIT Press, 1994.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(99)00278-9","volume":"245","author":"A. Maciel","year":"2000","unstructured":"A. Maciel, P. P\u00e9ladeau, and D. Th\u00e9rien. Programs over semigroups of dotdepth one. Theoretical Computer Science, 245:135\u2013148, 2000.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"30_CR18","first-page":"229","volume":"2","author":"R. L. Rivest","year":"1987","unstructured":"Ronald L. Rivest. Learning decision lists. Machine Learning, 2(3):229\u2013246, 1987.","journal-title":"Machine Learning"},{"key":"30_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BFb0055038","volume-title":"An algebraic approach to communication complexity","author":"J.-F. Raymond","year":"1998","unstructured":"J.-F. Raymond, P. Tesson, and D. Th\u00e9rien. An algebraic approach to communication complexity. In Proc. ICALP\u201998, Springer-Verlag LNCS, volume 1443, pages 29\u201340, 1998."},{"key":"30_CR20","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02194921","volume":"13","author":"M.P. Sch\u00fctzenberger","year":"1976","unstructured":"M.P. Sch\u00fctzenberger. Sur le produit de concat\u00e9nation non ambigu. Semigroup Forum, 13:47\u201375, 1976.","journal-title":"Semigroup Forum"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"H.U. Simon. Learning decision lists and trees with equivalence queries. In Proceedings of the 2nd European Conference on Computational Learning Theory (EuroCOLT\u201995), pages 322\u2013336, 1995.","DOI":"10.1007\/3-540-59119-2_188"},{"key":"30_CR22","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/0022-0000(93)90039-Y","volume":"47","author":"M. Szegedy","year":"1993","unstructured":"M. Szegedy. Functions with bounded symmetric communication complexity, programs over commutative monoids, and acc. Journal of Computer and System Sciences, 47:405\u2013423, 1993.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"30_CR23","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0304-3975(89)90051-0","volume":"64","author":"D. Th\u00e9rien","year":"1989","unstructured":"D. Th\u00e9rien. Programs over aperiodic monoids. Theoretical Computer Science, 64(3):271\u2013280, 29 1989.","journal-title":"Theoretical Computer Science"},{"key":"30_CR24","unstructured":"D. Th\u00e9rien and P. Tesson. Diamonds are forever: the DA variety. In submitted, 2001."},{"key":"30_CR25","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"L.G. Valiant. A theory of the learnable. Communications of the ACM, 27:1134\u20131142, 1984.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T09:48:30Z","timestamp":1685526510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_30","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}