{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T12:12:40Z","timestamp":1725538360923},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642044137"},{"type":"electronic","value":"9783642044144"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04414-4_19","type":"book-chapter","created":{"date-parts":[[2009,9,22]],"date-time":"2009-09-22T04:46:05Z","timestamp":1253594765000},"page":"201-215","source":"Crossref","is-referenced-by-count":2,"title":["An Algebraic Perspective on Boolean Function Learning"],"prefix":"10.1007","author":[{"given":"Ricard","family":"Gavald\u00e0","sequence":"first","affiliation":[]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","first-page":"1429","volume":"3612","author":"J. Almeida","year":"2009","unstructured":"Almeida, J., Margolis, S.W., Steinberg, B., Volkov, M.V.: Representation theory of finite semigroups, semigroup radicals and formal language theory. Trans. Amer. Math. Soc.\u00a03612, 1429\u20131461 (2009)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"1","key":"19_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1051\/ita:2005002","volume":"39","author":"J. Almeida","year":"2005","unstructured":"Almeida, J., Margolis, S.W., Volkov, M.V.: The pseudovariety of semigroups of triangular matrices over a finite field. RAIRO - Theoretical Informatics and Applications\u00a039(1), 31\u201348 (2005)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Information and Computation\u00a075, 87\u2013106 (1987)","journal-title":"Information and Computation"},{"key":"19_CR4","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Machine Learning\u00a02, 319\u2013342 (1988)","journal-title":"Machine Learning"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences\u00a038, 150\u2013164 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/337244.337257","volume":"47","author":"A. Beimel","year":"2000","unstructured":"Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: Learning functions represented as multiplicity automata. Journal of the ACM\u00a047, 506\u2013530 (2000)","journal-title":"Journal of the ACM"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/3-540-62685-9_13","volume-title":"Computational Learning Theory","author":"F. Bergadano","year":"1997","unstructured":"Bergadano, F., Bshouty, N.H., Tamon, C., Varricchio, S.: On learning branching programs and small depth circuits. In: Ben-David, S. (ed.) EuroCOLT 1997. LNCS, vol.\u00a01208, pp. 150\u2013161. Springer, Heidelberg (1997)"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Jackson, J.C.: On learning embedded symmetric concepts. In: COLT, pp. 337\u2013346 (1993)","DOI":"10.1145\/168304.168367"},{"key":"19_CR9","unstructured":"Bhshouty, N.H., Kushilevitz, E.: Learning from membership queries \/ online learning. Course notes in N. Bshouty\u2019s homepage"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0890-5401(90)90007-5","volume":"89","author":"D.A. Mix Barrington","year":"1990","unstructured":"Mix Barrington, D.A., Straubing, H., Th\u00e9rien, D.: Non-uniform automata over groups. Information and Computation\u00a089, 109\u2013132 (1990)","journal-title":"Information and Computation"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R. Beigel","year":"1994","unstructured":"Beigel, R., Tarui, J.: On ACC. Computational Complexity\u00a04, 350\u2013366 (1994)","journal-title":"Computational Complexity"},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1137\/S009753979326091X","volume":"25","author":"F. Bergadano","year":"1996","unstructured":"Bergadano, F., Varricchio, S.: Learning behaviors of automata from multiplicity and equivalence queries. SIAM Journal on Computing\u00a025, 1268\u20131280 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, A., Goyal, N., Pudl\u00e1k, P., Th\u00e9rien, D.: Lower bounds for circuits with mod m gates. In: FOCS, pp. 709\u2013718 (2006)","DOI":"10.1109\/FOCS.2006.46"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-540-70918-3_43","volume-title":"STACS 2007","author":"A. Chattopadhyay","year":"2007","unstructured":"Chattopadhyay, A., Krebs, A., Kouck\u00fd, M., Szegedy, M., Tesson, P., Th\u00e9rien, D.: Languages with bounded multiparty communication complexity. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 500\u2013511. Springer, Heidelberg (2007)"},{"issue":"3","key":"19_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0890-5401(89)90001-1","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D.: Learning decision trees from random examples. Information and Computation\u00a082(3), 231\u2013246 (1989)","journal-title":"Information and Computation"},{"key":"19_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/3-540-36494-3_30","volume-title":"STACS 2003","author":"R. Gavald\u00e0","year":"2003","unstructured":"Gavald\u00e0, R., Th\u00e9rien, D.: Algebraic characterizations of small classes of boolean functions. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 331\u2013342. Springer, Heidelberg (2003)"},{"issue":"2","key":"19_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.ic.2005.09.003","volume":"204","author":"R. Gavald\u00e0","year":"2006","unstructured":"Gavald\u00e0, R., Tesson, P., Th\u00e9rien, D.: Learning expressions and programs over monoids. Inf. Comput.\u00a0204(2), 177\u2013209 (2006)","journal-title":"Inf. Comput."},{"issue":"1","key":"19_CR18","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2007.05.018","volume":"384","author":"L. Hellerstein","year":"2007","unstructured":"Hellerstein, L., Servedio, R.A.: On pac learning algorithms for rich boolean function classes. Theor. Comput. Sci.\u00a0384(1), 66\u201376 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR19","first-page":"165","volume":"5","author":"D.P. Helmbold","year":"1990","unstructured":"Helmbold, D.P., Sloan, R.H., Warmuth, M.K.: Learning nested differences of intersection-closed concept classes. Machine Learning\u00a05, 165\u2013196 (1990)","journal-title":"Machine Learning"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Li, M., Pitt, L., Valiant, L.G.: On the learnability of boolean formulae. In: STOC, pp. 285\u2013295 (1987)","DOI":"10.1145\/28395.28426"},{"issue":"1","key":"19_CR21","doi-asserted-by":"publisher","first-page":"185","DOI":"10.4086\/toc.2006.v002a010","volume":"2","author":"A.R. Klivans","year":"2006","unstructured":"Klivans, A.R., Shpilka, A.: Learning restricted models of arithmetic circuits. Theory of Computing\u00a02(1), 185\u2013206 (2006)","journal-title":"Theory of Computing"},{"issue":"6","key":"19_CR22","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0020-0190(97)00026-4","volume":"61","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E.: A simple algorithm for learning o(log n)-term dnf. Inf. Process. Lett.\u00a061(6), 289\u2013292 (1997)","journal-title":"Inf. Process. Lett."},{"key":"#cr-split#-19_CR23.1","unstructured":"P??ladeau, P., Th??rien, D.: Sur les langages reconnus par des groupes nilpotents. Compte-rendus de l???Acad??mie des Sciences de Paris, 93???95 (1988);"},{"key":"#cr-split#-19_CR23.2","unstructured":"Translation to English as ECCC-TR01-040, Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"3","key":"19_CR24","first-page":"229","volume":"2","author":"R.L. Rivest","year":"1987","unstructured":"Rivest, R.L.: Learning decision lists. Machine Learning\u00a02(3), 229\u2013246 (1987)","journal-title":"Machine Learning"},{"key":"19_CR25","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF02194921","volume":"13","author":"M.P. Sch\u00fctzenberger","year":"1976","unstructured":"Sch\u00fctzenberger, M.P.: Sur le produit de concat\u00e9nation non ambigu. Semigroup Forum\u00a013, 47\u201375 (1976)","journal-title":"Semigroup Forum"},{"key":"19_CR26","first-page":"59","volume":"95","author":"A.A. Sherstov","year":"2008","unstructured":"Sherstov, A.A.: Communication lower bounds using dual polynomials. Bulletin of the EATCS\u00a095, 59\u201393 (2008)","journal-title":"Bulletin of the EATCS"},{"key":"19_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/3-540-59119-2_188","volume-title":"Computational Learning Theory","author":"H.-U. Simon","year":"1995","unstructured":"Simon, H.-U.: Learning decision lists and trees with equivalence-queries. In: Vit\u00e1nyi, P.M.B. (ed.) EuroCOLT 1995. LNCS, vol.\u00a0904, pp. 322\u2013336. Springer, Heidelberg (1995)"},{"key":"19_CR28","unstructured":"Tesson, P.: Computational Complexity Questions Related to Finite Monoids and Semigroups. PhD thesis, School of Computer Science, McGill University (2003)"},{"issue":"5-6","key":"19_CR29","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1142\/S0218196704001979","volume":"14","author":"P. Tesson","year":"2004","unstructured":"Tesson, P., Th\u00e9rien, D.: Monoids and computations. Intl. Journal of Algebra and Computation\u00a014(5-6), 801\u2013816 (2004)","journal-title":"Intl. Journal of Algebra and Computation"},{"issue":"2","key":"19_CR30","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s00224-004-1190-2","volume":"38","author":"P. Tesson","year":"2005","unstructured":"Tesson, P., Th\u00e9rien, D.: Complete classifications for the communication complexity of regular languages. Theory Comput. Syst.\u00a038(2), 135\u2013159 (2005)","journal-title":"Theory Comput. Syst."},{"key":"19_CR31","first-page":"37","volume":"88","author":"P. Tesson","year":"2006","unstructured":"Tesson, P., Th\u00e9rien, D.: Bridges between algebraic automata theory and complexity. Bull. of the EATCS\u00a088, 37\u201364 (2006)","journal-title":"Bull. of the EATCS"},{"key":"19_CR32","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Communications of the ACM\u00a027, 1134\u20131142 (1984)","journal-title":"Communications of the ACM"},{"issue":"3","key":"19_CR33","first-page":"229","volume":"2","author":"P. Weil","year":"1987","unstructured":"Weil, P.: Closure of varieties of languages under products with counter. J. of Comp. Syst. Sci.\u00a02(3), 229\u2013246 (1987)","journal-title":"J. of Comp. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04414-4_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:25:54Z","timestamp":1558538754000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04414-4_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642044137","9783642044144"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04414-4_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}