{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:39:25Z","timestamp":1648809565071},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00224-009-9233-3","type":"journal-article","created":{"date-parts":[[2009,7,31]],"date-time":"2009-07-31T14:48:49Z","timestamp":1249051729000},"page":"499-522","source":"Crossref","is-referenced-by-count":6,"title":["Arithmetizing Classes Around $\\textsf{NC}$ 1 and $\\textsf{L}$"],"prefix":"10.1007","volume":"46","author":[{"given":"Nutan","family":"Limaye","sequence":"first","affiliation":[]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,1]]},"reference":[{"issue":"2","key":"9233_CR1","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jcss.1999.1675","volume":"60","author":"M. Agrawal","year":"2000","unstructured":"Agrawal, M., Allender, E., Datta, S.: On TC0, AC0, and arithmetic circuits. J. Comput. Syst. Sci. 60(2), 395\u2013421 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"9233_CR2","unstructured":"Allender, E.: The division breakthroughs. Bull. Eur. Assoc. Theor. Comput. Sci. 74 (2001)"},{"key":"9233_CR3","series-title":"Quaderni di Matematica","first-page":"33","volume-title":"Complexity of Computations and Proofs","author":"E. Allender","year":"2004","unstructured":"Allender, E.: Arithmetic circuits and counting complexity classes. In: Krajicek, J. (ed.) Complexity of Computations and Proofs. Quaderni di Matematica, vol. 13, 33\u201372. Seconda Universita di Napoli, Naples (2004). An earlier version appeared in the Complexity Theory Column, SIGACT News 28(4) 2\u201315 (1997)"},{"key":"9233_CR4","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0304-3975(97)00227-2","volume":"209","author":"E. Allender","year":"1998","unstructured":"Allender, E., Jiao, J., Mahajan, M., Vinay, V.: Non-commutative arithmetic circuits: depth reduction and size lower bounds. Theor. Comput. Sci. 209, 47\u201386 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"9233_CR5","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proceedings of the ACM Symposium on Theory of Computing STOC, pp.\u00a0202\u2013211 (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"9233_CR6","doi-asserted-by":"crossref","unstructured":"Alur, R., Kumar, V., Madhusudan, P., Viswanathan, M.: Congruences for visibly pushdown languages. In: Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP), pp.\u00a01102\u20131114 (2005)","DOI":"10.1007\/11523468_89"},{"issue":"1","key":"9233_CR7","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A.M. Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9233_CR8","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"Borodin, A., Cook, S., Dymond, P., Ruzzo, W., Tompa, M.: Two applications of inductive counting for complementation problems. SIAM J. Comput. 18(3), 559\u2013578 (1989)","journal-title":"SIAM J. Comput."},{"key":"9233_CR9","doi-asserted-by":"crossref","unstructured":"Buss, S.: The Boolean formula value problem is in ALOGTIME. In: Proceedings of the ACM Symposium on Theory of Computing STOC, pp.\u00a0123\u2013131 (1987)","DOI":"10.1145\/28395.28409"},{"issue":"4","key":"9233_CR10","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"S. Buss","year":"1992","unstructured":"Buss, S., Cook, S., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM J. Comput. 21(4), 755\u2013780 (1992)","journal-title":"SIAM J. Comput."},{"key":"9233_CR11","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H. Caussinus","year":"1998","unstructured":"Caussinus, H., McKenzie, P., Th\u00e9rien, D., Vollmer, H.: Nondeterministic NC1 computation. J. Comput. Syst. Sci. 57, 200\u2013212 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9233_CR12","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1051\/ita:2001119","volume":"35","author":"A. Chiu","year":"2001","unstructured":"Chiu, A., Davida, G., Litow, B.: Division in logspace-uniform NC1. RAIRO Theor. Inf. Appl. 35, 259\u2013276 (2001)","journal-title":"RAIRO Theor. Inf. Appl."},{"key":"9233_CR13","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. Cook","year":"1971","unstructured":"Cook, S.: Characterizations of pushdown machines in terms of time-bounded computers. J. Assoc. Comput. Mach. 18, 4\u201318 (1971)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9233_CR14","doi-asserted-by":"crossref","unstructured":"Cook, S.: Deterministic CFL\u2019s are accepted simultaneously in polynomial time and log squared space. In: Proceedings of the ACM Symposium on Theory of Computing STOC, pp.\u00a0338\u2013345 (1979)","DOI":"10.1145\/800135.804426"},{"key":"9233_CR15","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(88)90148-2","volume":"26","author":"P.W. Dymond","year":"1988","unstructured":"Dymond, P.W.: Input-driven languages are in log\u2009n depth. Inf. Process. Lett. 26, 247\u2013250 (1988)","journal-title":"Inf. Process. Lett."},{"key":"9233_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0890-5401(89)90009-6","volume":"80","author":"P.W. Dymond","year":"1989","unstructured":"Dymond, P.W., Cook, S.: Complexity theory of parallel time and hardware. Inf. Comput. 80, 205\u2013226 (1989)","journal-title":"Inf. Comput."},{"key":"9233_CR17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/3-540-62034-6_57","volume-title":"Proceedings of the 16th Foundations of Software Technology and Theoretical Computer Science Conference FST&TCS","author":"H. Fernau","year":"1996","unstructured":"Fernau, H., Lange, K.-J., Reinhardt, K.: Advocating ownership. In: Proceedings of the 16th Foundations of Software Technology and Theoretical Computer Science Conference FST&TCS. LNCS, vol. 1180, pp. 286\u2013297. Springer, Berlin (1996)"},{"key":"9233_CR18","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/3-540-57163-9_25","volume-title":"Proceedings of the 9th International Symposium on Fundamentals of Computation Theory FCT","author":"M. Holzer","year":"1993","unstructured":"Holzer, M., Lange, K.-J.: On the complexities of linear LL(1) and LR(1) grammars. In: Proceedings of the 9th International Symposium on Fundamentals of Computation Theory FCT. LNCS, pp. 299\u2013308. Springer, Berlin (1993)"},{"key":"9233_CR19","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0020-0190(94)00036-0","volume":"50","author":"S. Istrail","year":"1994","unstructured":"Istrail, S., Zivkovic, D.: Bounded width polynomial size Boolean formulas compute exactly those functions in AC0. Inf. Process. Lett. 50, 211\u2013216 (1994)","journal-title":"Inf. Process. Lett."},{"key":"9233_CR20","series-title":"Algorithms and Complexity (A)","first-page":"67","volume-title":"Handbook of Theoretical Computer Science","author":"D.S. Johnson","year":"1990","unstructured":"Johnson, D.S.: A catalog of complexity classes. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Algorithms and Complexity (A), vol. A, pp. 67\u2013161. Elsevier\/MIT Press, Cambridge (1990)"},{"key":"9233_CR21","doi-asserted-by":"crossref","unstructured":"Lange, K.-J.: Complexity and structure in formal language theory. In: Proceedings of the IEEE Structure in Complexity Theory Conference, pp.\u00a0224\u2013230 (1993)","DOI":"10.1109\/SCT.1993.336523"},{"key":"9233_CR22","series-title":"LNCS","first-page":"477","volume-title":"Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science STACS","author":"N. Limaye","year":"2007","unstructured":"Limaye, N., Mahajan, M., Rao, B.V.R.: Arithmetizing classes around NC1 and AC1. In: Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science STACS. LNCS, vol. 4393, pp. 477\u2013488. Springer, Berlin (2007)"},{"key":"9233_CR23","series-title":"LNCS","volume-title":"Proceedings of the 3nd International Computer Science Symposium in Russia","author":"N. Limaye","year":"2008","unstructured":"Limaye, N., Mahajan, M., Meyer, A.: On the complexity of membership and counting in height-deterministic pushdown automata. In: Proceedings of the 3nd International Computer Science Symposium in Russia. LNCS, vol. 5010. Springer, Berlin (2008)"},{"key":"9233_CR24","unstructured":"Mahajan, M.: Polynomial size log depth circuits: between NC1 and AC1. Bull. Eur. Assoc. Theor. Comput. Sci. 91 (2007)"},{"key":"9233_CR25","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Proceedings of the 7th International Colloquium on Automata, Languages, and Programming ICALP","author":"K. Mehlhorn","year":"1980","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: Proceedings of the 7th International Colloquium on Automata, Languages, and Programming ICALP. LNCS, pp. 422\u2013432. Springer, Berlin (1980)"},{"issue":"2","key":"9233_CR26","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1006\/inco.1995.1064","volume":"118","author":"R. Niedermeier","year":"1995","unstructured":"Niedermeier, R., Rossmanith, P.: Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits. Inf. Comput. 118(2), 227\u2013245 (1995)","journal-title":"Inf. Comput."},{"issue":"11","key":"9233_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01205052","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N.: RL \u2286 SC. Comput. Complex. 4(11), 1\u201311 (1994)","journal-title":"Comput. Complex."},{"key":"9233_CR28","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W.L. Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. J. Comput. Syst. Sci. 21, 218\u2013235 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9233_CR29","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. Sudborough","year":"1978","unstructured":"Sudborough, I.: On the tape complexity of deterministic context-free language. J. Assoc. Comput. Mach. 25(3), 405\u2013414 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9233_CR30","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"42","author":"H. Venkateswaran","year":"1991","unstructured":"Venkateswaran, H.: Properties that characterize $\\textsf{LogCFL}$ . J. Comput. Syst. Sci. 42, 380\u2013404 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9233_CR31","doi-asserted-by":"crossref","unstructured":"Vinay, V.: Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In: Proceedings of 6th IEEE Structure in Complexity Theory Conference, pp.\u00a0270\u2013284 (1991)","DOI":"10.1109\/SCT.1991.160269"},{"key":"9233_CR32","doi-asserted-by":"crossref","unstructured":"Vinay, V.: Hierarchies of circuit classes that are closed under complement. In: Proceedings of the 11th Annual IEEE Conference on Computational Complexity CCC, Washington, DC, USA, pp.\u00a0108\u2013117 (1996)","DOI":"10.1109\/CCC.1996.507674"},{"key":"9233_CR33","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, New York (1999)"},{"key":"9233_CR34","series-title":"LNCS","first-page":"40","volume-title":"Proceedings of the Fundamentals of Computation Theory Conference FCT","author":"B. Braunm\u00fchl Von","year":"1983","unstructured":"Von Braunm\u00fchl, B., Verbeek, R.: Input-driven languages are recognized in log\u2009n space. In: Proceedings of the Fundamentals of Computation Theory Conference FCT. LNCS, pp. 40\u201351. Springer, Berlin (1983)"},{"key":"9233_CR35","first-page":"573","volume-title":"Synthesis of Parallel Algorithms","author":"J. Gathen Von zur","year":"1993","unstructured":"Von zur Gathen, J.: Parallel linear algebra. In: Reif, J.H. (ed.) Synthesis of Parallel Algorithms, pp. 573\u2013617. Morgan Kaufmann, San Mateo (1993)"},{"issue":"1","key":"9233_CR36","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/0890-5401(91)90078-G","volume":"91","author":"J. Gathen Von zur","year":"1991","unstructured":"Von zur Gathen, J., Seroussi, G.: Boolean circuits versus arithmetic circuits. Inf. Comput. 91(1), 142\u2013154 (1991)","journal-title":"Inf. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9233-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9233-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9233-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:38Z","timestamp":1558698698000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9233-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,1]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9233"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9233-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,1]]}}}