{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:55:40Z","timestamp":1743040540471,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319214993"},{"type":"electronic","value":"9783319215006"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21500-6_27","type":"book-chapter","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T08:07:44Z","timestamp":1437120464000},"page":"340-351","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Distinguishing NC $$^1$$ and NL"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Krebs","sequence":"first","affiliation":[]},{"given":"Klaus-J\u00f6rn","family":"Lange","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Ludwig","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,18]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, June 13\u201316, pp. 202\u2013211. ACM, Chicago (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.M., Compton, K.J., Straubing, H., Th\u00e9rien, D.: Regular Languages in NC\n$${^1}$$\n. J. Comput. Syst. Sci. 44(3), 478\u2013499 (1992)","DOI":"10.1016\/0022-0000(92)90014-A"},{"key":"27_CR3","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":"5","key":"27_CR4","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0020-0190(88)90148-2","volume":"26","author":"PW Dymond","year":"1988","unstructured":"Dymond, P.W.: Input-Driven Languages are in log n Depth. Inf. Process. Lett. 26(5), 247\u2013250 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"27_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"ML Furst","year":"1984","unstructured":"Furst, M.L., Saxe, J.B., Sipser, M.: Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory 17(1), 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: Hartmanis, J. (ed.) Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28\u201330, pp. 6\u201320. ACM, Berkeley (1986)","DOI":"10.1145\/12130.12132"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-642-31653-1_17","volume-title":"Developments in Language Theory","author":"A Krebs","year":"2012","unstructured":"Krebs, A., Lange, K.-J.: Dense completeness. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 178\u2013189. Springer, Heidelberg (2012)"},{"key":"27_CR8","unstructured":"Krebs, A., Lange, K.-L., 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, March 4\u20137. LIPIcs, vol. 30, pp. 594\u2013607. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Garching (2015)"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Pebbling moutain ranges and its application of DCFL-Recognition. In: de Bakker, J.W., van Leeuwen, J. (eds) Proceedings of the Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, July 14\u201318, The Netherland. LNCS, vol. 85, pp. 422\u2013435. Springer, Heidelberg (1980)","DOI":"10.1007\/3-540-10003-2_89"},{"key":"27_CR10","volume-title":"Mathematical Theory of L Systems","author":"G Rozenberg","year":"1980","unstructured":"Rozenberg, G., Salomaa, A.: Mathematical Theory of L Systems. Academic Press Inc., Orlando (1980)"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: Aho, A.V. (ed.) Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 77\u201382. ACM, New York (1987)","DOI":"10.1145\/28395.28404"},{"issue":"5","key":"27_CR12","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/0020-0190(75)90027-7","volume":"3","author":"J van Leeuwen","year":"1975","unstructured":"van Leeuwen, J.: The Membership Question for ET0L-Languages is Polynomially Complete. Inf. Process. Lett. 3(5), 138\u2013143 (1975)","journal-title":"Inf. Process. Lett."},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"van Leeuwen, J.: Variations of a new machine model. In: 17th Annual Symposium on Foundations of Computer Science, October 25\u201327, pp. 228\u2013235. IEEE Computer Society, Texas (1976)","DOI":"10.1109\/SFCS.1976.35"},{"key":"27_CR14","unstructured":"Vollmer, H.: The gap-language-technique revisited. In: B\u00f6rger, E., B\u00f6uning, H.K., Richter, M.M., Sch\u00f6nfeld, W. (eds) CSL 1990. LNCS, vol. 533, pp. 389\u2013399. Springer, Heidelberg (1990)"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to circuit complexity - a uniform approach. Texts in theoretical computer science. Springer (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21500-6_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T09:50:18Z","timestamp":1676973018000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21500-6_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319214993","9783319215006"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21500-6_27","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":"18 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}