{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:00:23Z","timestamp":1725512423970},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797081"},{"type":"electronic","value":"9783540797098"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79709-8_25","type":"book-chapter","created":{"date-parts":[[2008,5,13]],"date-time":"2008-05-13T14:33:17Z","timestamp":1210689197000},"page":"240-251","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Nutan","family":"Limaye","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"25_CR1","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/321906.321913","volume":"22","author":"I.H. Sudborough","year":"1975","unstructured":"Sudborough, I.H.: A note on tape-bounded complexity classes and linear context-free languages. JACM\u00a022(4), 499\u2013500 (1975)","journal-title":"JACM"},{"issue":"3","key":"25_CR2","doi-asserted-by":"publisher","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. JACM\u00a025(3), 405\u2013414 (1978)","journal-title":"JACM"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(88)90047-6","volume":"29","author":"O. Ibarra","year":"1988","unstructured":"Ibarra, O., Jiang, T., Ravikumar, B.: Some subclasses of context-free languages in NC\n                  1. IPL\u00a029, 111\u2013117 (1988)","journal-title":"IPL"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/3-540-57163-9_25","volume-title":"Fundamentals of Computation Theory","author":"M. Holzer","year":"1993","unstructured":"Holzer, M., Lange, K.J.: On the complexities of linear LL(1) and LR(1) grammars. In: \u00c9sik, Z. (ed.) FCT 1993. LNCS, vol.\u00a0710, pp. 299\u2013308. Springer, Heidelberg (1993)"},{"issue":"1","key":"25_CR5","first-page":"150","volume":"38","author":"D. Barrington","year":"1989","unstructured":"Barrington, D.: Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1. JCSS\u00a038(1), 150\u2013164 (1989)","journal-title":"JCSS"},{"key":"25_CR6","first-page":"224","volume-title":"8th CoCo","author":"K.J. Lange","year":"1993","unstructured":"Lange, K.J.: Complexity and structure in formal language theory. In: 8th CoCo, pp. 224\u2013238. IEEE Computer Society, Los Alamitos (1993)"},{"key":"25_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol.\u00a085, pp. 422\u2013432. Springer, Heidelberg (1980)"},{"key":"25_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/3-540-12689-9_92","volume-title":"Foundations of Computation Theory","author":"B.V. Braunmuhl","year":"1983","unstructured":"Braunmuhl, B.V., Verbeek, R.: Input-driven languages are recognized in log n space. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol.\u00a0158, pp. 40\u201351. Springer, Heidelberg (1983)"},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0020-0190(88)90148-2","volume":"26","author":"P. Dymond","year":"1988","unstructured":"Dymond, P.: Input-driven languages are in logn depth. IPL\u00a026, 247\u2013250 (1988)","journal-title":"IPL"},{"key":"25_CR10","first-page":"202","volume-title":"36th STOC","author":"R. Alur","year":"2004","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: 36th STOC, pp. 202\u2013211. ACM, New York (2004)"},{"issue":"2","key":"25_CR11","first-page":"200","volume":"57","author":"H. Caussinus","year":"1998","unstructured":"Caussinus, H., McKenzie, P., Th\u00e9rien, D., Vollmer, H.: Nondeterministic NC\n                  1 computation. JCSS\u00a057(2), 200\u2013212 (1998)","journal-title":"JCSS"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-70918-3_41","volume-title":"STACS 2007","author":"N. Limaye","year":"2007","unstructured":"Limaye, N., Mahajan, M., Rao, B.V.R.: Arithmetizing classes arround NC1 and L. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 477\u2013488. Springer, Heidelberg (2007)"},{"key":"25_CR13","unstructured":"Limaye, N., Mahajan, M., Rao, B.V.R.: Arithmetizing classes arround NC1 and L. Technical Report ECCC TR07- (2007) submitted to TCS (spl.issue for STACS 2007) (2007)"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-540-74456-6_13","volume-title":"Mathematical Foundations of Computer Science 2007","author":"D. Nowotka","year":"2007","unstructured":"Nowotka, D., Srba, J.: Height-deterministic pushdown automata. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 125\u2013134. Springer, Heidelberg (2007)"},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/11779148_12","volume-title":"Developments in Language Theory","author":"D. Caucal","year":"2006","unstructured":"Caucal, D.: Synchronization of pushdown automata. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 120\u2013132. Springer, Heidelberg (2006)"},{"key":"25_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11779148_1","volume-title":"Developments in Language Theory","author":"R. Alur","year":"2006","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 1\u201313. Springer, Heidelberg (2006)"},{"key":"25_CR17","unstructured":"Blass, A., Gurevich, Y.: A note on nested words. Technical Report MSR-TR-2006-139, Microsoft Research (October 2006)"},{"key":"25_CR18","first-page":"123","volume-title":"19th STOC","author":"S. Buss","year":"1987","unstructured":"Buss, S.: The Boolean formula value problem is in ALOGTIME. In: 19th STOC, pp. 123\u2013131. ACM, New York (1987)"},{"key":"25_CR19","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, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79709-8_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:28:48Z","timestamp":1619522928000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79709-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797081","9783540797098"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79709-8_25","relation":{},"subject":[]}}