{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:47:00Z","timestamp":1725536820360},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"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-03816-7_8","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"78-89","source":"Crossref","is-referenced-by-count":0,"title":["Arithmetic Circuits, Monomial Algebras and Finite Automata"],"prefix":"10.1007","author":[{"given":"Vikraman","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pushkar S.","family":"Joglekar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"8_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient String Matching: An Aid to Bibliographic Search. Commun. ACM\u00a018(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-540-85363-3_23","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Arvind","year":"2008","unstructured":"Arvind, V., Mukhopadhyay, P.: Derandomizing the isolation lemma and lower bounds for circuit size. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 276\u2013289. Springer, Heidelberg (2008)"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Arvind, V., Mukhopadhyay, P., Srinivasan, S.: New results on Noncommutative Polynomial Identity Testing. In: Proc. of Annual IEEE Conference on Computational Complexity, pp. 268\u2013279 (2008)","DOI":"10.1109\/CCC.2008.22"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Wee, H.: More on Noncommutative Polynomial Identity Testing. In: Proc. of 20th Annual Conference on Computational Complexity, pp. 92\u201399 (2005)","DOI":"10.1109\/CCC.2005.13"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Chien, S., Sinclair, A.: Algebras with polynomial identities and computing the determinant. In: Proc. Annual IEEE Sym. on Foundations of Computer Science, pp. 352\u2013361 (2004)","DOI":"10.1109\/FOCS.2004.9"},{"key":"8_CR6","unstructured":"Hopcroft, J.E., Motawani, R., Ullman, J.D.: Introduction to Automata Theory Languages and Computation, 2nd edn. Pearson Education Publishing Company, London"},{"issue":"4","key":"8_CR7","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which Problems Have Strongly Exponential Complexity? Journal Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal Computer and System Sciences"},{"issue":"3","key":"8_CR8","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1145\/322326.322341","volume":"29","author":"M. Jerrum","year":"1982","unstructured":"Jerrum, M., Snir, M.: Some Exact Complexity Results for Straight-Line Computations over Semirings. J. ACM\u00a029(3), 874\u2013897 (1982)","journal-title":"J. ACM"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomization of polynomial identity test means proving circuit lower bounds. In: Proc. of 35th ACM Sym. on Theory of Computing, pp. 355\u2013364 (2003)","DOI":"10.1145\/780542.780595"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Koch, R., Blum, N.: Greibach Normal Form Transformation. In: STACS, pp. 47\u201354 (1997)","DOI":"10.1007\/BFb0023447"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Klivans, A., Spielman, D.A.: Randomness efficient identity testing of multivariate polynomials. In: STOC 2001, pp. 216\u2013223 (2001)","DOI":"10.1145\/380752.380801"},{"key":"8_CR12","unstructured":"Mahajan, M., Vinay, V.: A Combinatorial Algorithm for the Determinant. In: SODA 1997, pp. 730\u2013738 (1997)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching Is as Easy as Matrix Inversion. In: STOC 1987, pp. 345\u2013354 (1987)","DOI":"10.1145\/28395.383347"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for noncommutative computation. In: Proc. of 23rd ACM Sym. on Theory of Computing, pp. 410\u2013418 (1991)","DOI":"10.1145\/103418.103462"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/321406.321412","volume":"14","author":"D.J. Rosenkrantz","year":"1967","unstructured":"Rosenkrantz, D.J.: Matrix equations and normal forms for context-free grammars. J. ACM\u00a0(14), 501\u2013507 (1967)","journal-title":"J. ACM"},{"issue":"1","key":"8_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R. Raz","year":"2005","unstructured":"Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non commutative models. Computational Complexity\u00a014(1), 1\u201319 (2005)","journal-title":"Computational Complexity"},{"key":"8_CR17","unstructured":"Toda, S.: Counting Problems Computationally Equivalent to the Determinant (manuscript)"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Vinay, V.: Counting Auxiliary Pushdown Automata and Semi-unbounded Arithmetic Circuits. In: Proc. 6th Structures in Complexity Theory Conference, pp. 270\u2013284 (1991)","DOI":"10.1109\/SCT.1991.160269"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T02:33:56Z","timestamp":1558492436000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}