{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T21:05:06Z","timestamp":1761944706470,"version":"build-2065373602"},"publisher-location":"New York, NY","reference-count":24,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9780387968186"},{"type":"electronic","value":"9780387347707"}],"license":[{"start":{"date-parts":[[1988,1,1]],"date-time":"1988-01-01T00:00:00Z","timestamp":567993600000},"content-version":"tdm","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":[[1988]]},"DOI":"10.1007\/bfb0040374","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T00:03:50Z","timestamp":1154563430000},"page":"64-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On some languages in NC"],"prefix":"10.1007","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bala","family":"Ravikumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jik H.","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"unstructured":"Allender, E., P-uniform circuit complexity, Tech. Report, Department of Comp. Science, The Rutgers University, DCS-TR-198.","key":"7_CR1"},{"doi-asserted-by":"crossref","unstructured":"Alt, H., Eine untere Schranke fur den Platzbedarf bei der Analyse beschrankter kontextfreier Sprachen, Dissertation, Saarbrucken, (1976).","key":"7_CR2","DOI":"10.1007\/3-540-08138-0_10"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF00264016","volume":"12","author":"H. Alt","year":"1979","unstructured":"Alt, H., Lower bounds on space complexity for context-free recognition, Acta Informatica 12, (1979), pp. 33\u201361.","journal-title":"Acta Informatica"},{"unstructured":"Barrington, D., Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Proc. 18th Annual Symp. on Theory of Computing (1986), pp. 1\u20135","key":"7_CR4"},{"unstructured":"Buss, S., Boolean formula-value problem is in ALOGTIME, Proc. of 19th Annual Symp. on Theory of Computing (1987), pp. 123\u2013131.","key":"7_CR5"},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., D. Kozen, and L. Stockmeyer, Alternation, J. ACM 28, 1 (1981), pp. 114\u2013133.","journal-title":"J. ACM"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(86)90112-X","volume":"44","author":"J. Chang","year":"1986","unstructured":"Chang, J., O. Ibarra, M. Palis, and B. Ravikumar, On pebble automata, TCS 44 (1986), pp. 111\u2013121.","journal-title":"TCS"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"Cook, S., A taxonomy of problems with fast parallel algorithms, Information and Control 64 (1985), pp. 2\u201322.","journal-title":"Information and Control"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/S0019-9958(68)90901-7","volume":"13","author":"M. Harrison","year":"1968","unstructured":"Harrison, M. and O. Ibarra, Multitape and multihead pushdown automata, Information and Control 13 (1968), pp. 433\u2013470.","journal-title":"Information and Control"},{"unstructured":"Harrison, M., Introduction to Formal Language Theory, Addison-Wesley (1978).","key":"7_CR10"},{"unstructured":"Hopcroft, J. and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley (1979).","key":"7_CR11"},{"key":"7_CR12","first-page":"153","volume":"13","author":"O. Ibarra","year":"1976","unstructured":"Ibarra, O. and C. Kim, A useful device for showing the solvability of some decision problems, JCSS 13 (1976), pp. 153\u2013160.","journal-title":"JCSS"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"O. Ibarra","year":"1978","unstructured":"Ibarra, O., Reversal-bounded multicounter machines and their decision problems, JACM 25 (1978), pp. 116\u2013133.","journal-title":"JACM"},{"key":"7_CR14","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"R. Ladner","year":"1984","unstructured":"Ladner, R., R. Lipton, and L. Stockmeyer, Alternating pushdown and stack automata, SICOMP 13 (1984), pp. 135\u2013155.","journal-title":"SICOMP"},{"doi-asserted-by":"crossref","unstructured":"Lewis, P., J. Hartmanis, and R. Stearns, Memory bounds for the recognition of context-free and context-sensitive languages, IEEE Conf. Record on Switching Circuit Theory and Logical Design, pp. 191\u2013202.","key":"7_CR15","DOI":"10.1109\/FOCS.1965.14"},{"key":"7_CR16","first-page":"11","volume":"18","author":"B. Litow","year":"1985","unstructured":"Litow, B., On efficient deterministic simulation of Turing machine computations below logspace, MST 18 (1985), pp. 11\u201318.","journal-title":"MST"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24","author":"N. Lynch","year":"1977","unstructured":"Lynch, N., Log space recognition and translation of parenthesis languages, JACM 24 (1977), pp. 583\u2013590.","journal-title":"JACM"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(82)90075-5","volume":"21","author":"B. Monien","year":"1982","unstructured":"Monien, B. and I. Sudborough, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, TCS 21 (1982), pp. 237\u2013253.","journal-title":"TCS"},{"unstructured":"Pippenger, N., On simultaneous resource bounds, Twentieth IEEE Foundations of Computer Science (1979) pp. 307\u2013310.","key":"7_CR19"},{"key":"7_CR20","first-page":"365","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"Ruzzo, W., On uniform circuit complexity, JCSS 22 (1981), pp. 365\u2013383.","journal-title":"JCSS"},{"key":"7_CR21","first-page":"177","volume":"4","author":"W. Savitch","year":"1970","unstructured":"Savitch, W., Relationships between nondeterministic and deterministic tape complexities, JCSS 4 (1970), pp. 177\u2013192.","journal-title":"JCSS"},{"key":"7_CR22","first-page":"313","volume":"4","author":"F. Springsteel","year":"1972","unstructured":"Springsteel, F. and R. Ritchie, Language recognition by marking automata, Information and Control 4 (1972), pp. 313\u2013330.","journal-title":"Information and Control"},{"key":"7_CR23","first-page":"62","volume":"10","author":"I. Sudborough","year":"1975","unstructured":"Sudborough, I., Tape-bounded complexity classes and multihead finite automata, JCSS 10 (1975), pp. 62\u201376.","journal-title":"JCSS"},{"issue":"2","key":"7_CR24","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0020-0190(81)90013-2","volume":"12","author":"M. Tompa","year":"1981","unstructured":"Tompa, M., An extension of Savitch's theorem to small space bounds, IPL 12, 2 (1981), pp. 106\u2013108.","journal-title":"IPL"}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0040374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T09:17:09Z","timestamp":1736500629000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040374"}},"subtitle":["Extended abtract"],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9780387968186","9780387347707"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0040374","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}