{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T05:27:16Z","timestamp":1737523636270,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671596"},{"type":"electronic","value":"9783540465218"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46521-9_8","type":"book-chapter","created":{"date-parts":[[2007,11,3]],"date-time":"2007-11-03T22:47:16Z","timestamp":1194130036000},"page":"87-101","source":"Crossref","is-referenced-by-count":0,"title":["Semantical Counting Circuits"],"prefix":"10.1007","author":[{"given":"Fabrice","family":"Noilhan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,2,14]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender, A. Ambainis, D.M. Barrington, S. Datta, and H. L\u00eaThanh. Bounded depth arithmetic circuits: Counting and closure. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming, pages 149\u2013158, 1999.","DOI":"10.1007\/3-540-48523-6_12"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"M. Agrawal, E. Allender, and S. Datta. On TC 0, AC 0, and arithmetic circuits. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity, pages 134\u2013148, 1997.","DOI":"10.1109\/CCC.1997.612309"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"A. Ambainis, D.M. Barrington, and H. L\u00eaThanh. On counting AC 0 circuits with negated constants. In Proceedings of the 23th ACM Symposium on Mathematical Foundations of Computer Science, pages 409\u2013417, 1998.","DOI":"10.1007\/BFb0055790"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"Alvarez","year":"1993","unstructured":"Alvarez and Jenner. A very hard log-space counting class. Theoretical Computer Science, 107:3\u201330, 1993.","journal-title":"Theoretical Computer Science"},{"key":"8_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ro\/1996300100011","volume":"30","author":"E. Allender","year":"1996","unstructured":"E. Allender and M. Ogihara. Relationships among PL, #L, and the determinant. RAIRO, 30:1\u201321, 1996.","journal-title":"RAIRO"},{"key":"8_CR6","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 NC 1. Journal of Computer and System Sciences, 38:150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H. Caussinus","year":"1998","unstructured":"H. Caussinus, P. McKenzie, D. Th\u00e9rien, and H. Vollmer. Nondeterministic NC 1 computation. Journal of Computer and System Sciences, 57:200\u2013212, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"S.A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"key":"8_CR9","unstructured":"C. Damm. DET = L #L. Informatik-Preprint, Fachbereich Informatik der Humboldt-Universit\u00e4t zu Berlin 8, 1991."},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. A. Fenner","year":"1994","unstructured":"S. A. Fenner, L. J. Fortnow, and S. A. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1):116\u2013148, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR11","first-page":"67","volume":"A","author":"D.S. Johnson","year":"1990","unstructured":"D.S. Johnson. A catalog of complexity classes. Handbook of Theoretical Computer Science, A:67\u2013161, 1990.","journal-title":"Handbook of Theoretical Computer Science"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"M. Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chicago Journal of Theoretical Computer Science, December 1997.","DOI":"10.4086\/cjtcs.1997.005"},{"issue":"3","key":"8_CR13","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1006\/jcss.1995.1039","volume":"50","author":"S. Saluja","year":"1995","unstructured":"S. Saluja, K. V. Subrahmanyam, and M. N. Thakur. Descriptive complex-ity of #P functions. Journal of Computer and System Sciences, 50(3):493\u2013505, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/PL00001596","volume":"7","author":"M. Santha","year":"1998","unstructured":"M. Santha and S. Tan. Verifying the determinant in parallel. Computational Complexity, 7:128\u2013151, 1998.","journal-title":"Computational Complexity"},{"key":"8_CR15","unstructured":"S. Toda. Counting problems computationally equivalent to computing the determinant. Tech. Rep. CSIM 91-07, 1991."},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"L.G. Valiant. Why is boolean complexity theory difficult? London Math-ematical Society Lecture Notes Series, 16(9), 1992.","DOI":"10.1017\/CBO9780511526633.008"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1137\/0221040","volume":"21","author":"H. Venkateswaran","year":"1992","unstructured":"H. Venkateswaran. Circuit definitions of nondeterministic complexity classes. SIAM Journal on Computing, 21:665\u2013670, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of the 6th Annual IEEE Conference on Structure in Complexity Theory, pages 270\u2013284, 1991.","DOI":"10.1109\/SCT.1991.160269"},{"issue":"1\u20132","key":"8_CR20","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0304-3975(95)00237-5","volume":"163","author":"H. Vollmer","year":"1996","unstructured":"H. Vollmer and K.W. Wagner. Recursion theoretic characterizations of complexity classes of counting functions. Theoretical Computer Science, 163(1\u20132):245\u2013258, 1996.","journal-title":"Theoretical Computer Science"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"I. Wegener. The complexity of boolean functions. Wiley-Teubner series in computer science, 1987.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"8_CR22","unstructured":"T. Yamakami. Uniform AC 0 counting circuits. Manuscript, 1996."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46521-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T02:36:13Z","timestamp":1737513373000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46521-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671596","9783540465218"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-46521-9_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}