{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:42:23Z","timestamp":1725468143136},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540647812"},{"type":"electronic","value":"9783540686811"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055038","type":"book-chapter","created":{"date-parts":[[2006,8,1]],"date-time":"2006-08-01T12:08:05Z","timestamp":1154434085000},"page":"29-40","source":"Crossref","is-referenced-by-count":11,"title":["An algebraic approach to communication complexity"],"prefix":"10.1007","author":[{"given":"Jean-Fran\u00c7ois","family":"Raymond","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Tesson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"issue":"2","key":"3_CR1","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. Syst. Sci., 45(2):204\u2013232, Oct. 1992.","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"3_CR2","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. J. Comput. Syst. Sci., 38(1):150\u2013164, Feb. 1989.","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"3_CR3","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. M. Barrington, H. Straubing, and D. Th\u00e9rien. Non-uniform automata over groups. Information and Computation, 89(2):109\u2013132, Dec. 1990.","journal-title":"Information and Computation"},{"issue":"4","key":"3_CR4","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. A. M. Barrington","year":"1988","unstructured":"D. A. M. Barrington and D. Th\u00e9rien. Finite monoids and the fine structure of NC1. Journal of the ACM, 35(4):941\u2013952, Oct. 1988.","journal-title":"Journal of the ACM"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, M. L. Furst, and R. J. Lipton. Multi-party protocols. In Proc. 15th ACM STOC, pages 94\u201399, 1983.","DOI":"10.1145\/800061.808737"},{"key":"3_CR6","unstructured":"S. Eilenberg. Automata, Languages and Machines, volume B. Academic Press, 1976."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"V. Grolmusz. Separating the communication complexities of MOD m and MOD p circuits. In Proc. 33rd IEEE FOCS, pages 278\u2013287, 1992.","DOI":"10.1109\/SFCS.1992.267764"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"V. Grolmusz. A weight-size trade-off for circuits and MOD m gates. In Proc. 26th ACM STOC, pages 68\u201374, 1994.","DOI":"10.1145\/195058.195108"},{"key":"3_CR9","first-page":"610","volume":"II","author":"J. H\u00e5stad","year":"1990","unstructured":"J. H\u00e5stad and M. Goldmann. On the power of small-depth threshold circuits. In Proc. 31st IEEE FOCS, volume II, pages 610\u2013618, 1990.","journal-title":"Proc. 31st IEEE FOCS"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"M. Karchmer and A. Wigderson. Monotone circuits for connectivity require superlogarithmic depth. In Proc. 20th ACM STOC, pages 539\u2013550, 1988.","DOI":"10.1145\/62212.62265"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"3_CR12","unstructured":"L. Lov\u00e1sz. Communication complexity: a survey. Technical Report CS-TR-204-89, Princeton University, 1989."},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/BF01212963","volume":"1","author":"P. McKenzie","year":"1991","unstructured":"P. McKenzie, P. P\u00e9ladeau, and D. Th\u00e9rien. NC1: The automata theoretic viewpoint. Computational Complexity, 1:330\u2013359, 1991.","journal-title":"Computational Complexity"},{"key":"3_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of formal languages","author":"J.-E. Pin","year":"1986","unstructured":"J.-E. Pin. Varieties of formal languages. North Oxford Academic Publishers Ltd, London, 1986."},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0022-4049(88)90097-7","volume":"52","author":"J.-\u00e9. Pin","year":"1988","unstructured":"J.-\u00e9. Pin, H. Straubing, and D. Th\u00e9rien. Locally trivial categories and unambiguous concatenation. J. Pure Applied Algebra, 52:297\u2013311, 1988.","journal-title":"J. Pure Applied Algebra"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"R. Raz and P. McKenzie. Separation of the monotone NC hierarchy. In Proc. 38th IEEE FOCS, 1997.","DOI":"10.1109\/SFCS.1997.646112"},{"issue":"3","key":"3_CR17","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. J. Comput. Syst. Sci., 47(3):405\u2013423, 1993.","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"D. Th\u00e9rien. Subword counting and nilpotent groups. In L. Cummings, editor, Combinatorics on Words: Progress and Perspectives, pages 195\u2013208. Academic Press, 1983.","DOI":"10.1016\/B978-0-12-198820-3.50021-8"},{"issue":"3","key":"3_CR19","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 May 1989.","journal-title":"Theoretical Computer Science"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"A. C. Yao. Some complexity questions related to distributive computing. In Proc. 11th ACM STOC, pages 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T12:18:58Z","timestamp":1555762738000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540647812","9783540686811"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0055038","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}