{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:27:56Z","timestamp":1742912876502,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480533"},{"type":"electronic","value":"9783662480540"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_32","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T11:57:29Z","timestamp":1439207849000},"page":"384-394","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Visibly\u00a0Counter\u00a0Languages and\u00a0the\u00a0Structure\u00a0of\u00a0$$\\mathrm {NC}^{1}$$"],"prefix":"10.1007","author":[{"given":"Michael","family":"Hahn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus-J\u00f6rn","family":"Lange","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Ludwig","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Babai, L. (eds.) STOC, pp. 202\u2013211. ACM (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/11672142_34","volume-title":"STACS 2006","author":"V B\u00e1r\u00e1ny","year":"2006","unstructured":"B\u00e1r\u00e1ny, V., L\u00f6ding, C., Serre, O.: Regularity problems for visibly pushdown languages. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 420\u2013431. Springer, Heidelberg (2006)"},{"issue":"1","key":"32_CR3","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"A David","year":"1989","unstructured":"David, A., Barrington, M.: Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC$$^1$$. J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"32_CR4","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"A David","year":"1992","unstructured":"David, A., Th\u00e9rien, D., Straubing, H., Compton, K.J., Barrington, M.: Regular Languages in NC$$^1$$. J. Comput. Syst. Sci. 44(3), 478\u2013499 (1992)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"32_CR5","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"A David","year":"1988","unstructured":"David, A., Th\u00e9rien, D., Barrington, M.: Finite monoids and the fine structure of NC$$^{\\text{1 }}$$. J. ACM 35(4), 941\u2013952 (1988)","journal-title":"J. ACM"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. In: FOCS, pp. 260\u2013270 (1981)","DOI":"10.1109\/SFCS.1981.35"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: STOC, pp. 6\u201320. ACM (1986)","DOI":"10.1145\/12130.12132"},{"key":"32_CR8","unstructured":"Krebs, A., Lange, K., Ludwig, M.: Visibly Counter Languages and Constant Depth Circuits. In: Mayr, E.W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Garching, Germany, vol. 30 of LIPIcs, pp. 594\u2013607. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 4\u20137 March 2015"},{"issue":"7","key":"32_CR9","doi-asserted-by":"publisher","first-page":"3186","DOI":"10.1137\/080741811","volume":"39","author":"P McKenzie","year":"2010","unstructured":"McKenzie, P., Thomas, M., Vollmer, H.: Extensional uniformity for boolean circuits. SIAM J. Comput. 39(7), 3186\u20133206 (2010)","journal-title":"SIAM J. Comput."},{"key":"32_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Automata Languages and Programming","author":"K Mehlhorn","year":"1980","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: de Bakker, J., van Leeuwen, J. (eds.) Automata Languages and Programming. LNCS, pp. 422\u2013435. Springer, Berlin Heidelberg (1980)"},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: STOC, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"32_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H Straubing","year":"1994","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston (1994)"},{"key":"32_CR13","series-title":"Texts in theoretical computer science","doi-asserted-by":"publisher","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. Texts in theoretical computer science. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T06:15:18Z","timestamp":1676960118000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}