{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:25:29Z","timestamp":1725456329993},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540634379"},{"type":"electronic","value":"9783540695479"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0029973","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T06:24:59Z","timestamp":1133418299000},"page":"299-308","source":"Crossref","is-referenced-by-count":2,"title":["Multi-head finite automata: Data-independent versus data-dependent computations"],"prefix":"10.1007","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3.Structural Complexity I, volume 11 of EATCS Monographs on Theoretical Computer Science. Springer, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. A. Barrington","year":"1989","unstructured":"D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences, 38:150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. A. M. Barrington","year":"1990","unstructured":"D. A. M. Barrington, N. Immerman, and H.Straubing. On uniformity within NC1. Journal of Computer and System Sciences, 41:274\u2013306, 1990.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR4","first-page":"149","volume-title":"Proceedings of the 20th Conference on Mathematical Foundations of Computer Science","author":"C. Damm","year":"1995","unstructured":"C. Damm and M. Holzer. Automata that take advice. In J. Wiedermann and P. H\u00e1jek, editors, Proceedings of the 20th Conference on Mathematical Foundations of Computer Science, number 969 in LNCS, pages 149\u2013158, Prague, Czech Republic, August 1995. Springer."},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J. Hartmanis","year":"1972","unstructured":"J. Hartmanis. On non-determinancy in simple computing devices. Acta Informatica, 1:336\u2013344, 1972.","journal-title":"Acta Informatica"},{"key":"30_CR6","first-page":"191","volume":"28","author":"R. M. Karp","year":"1982","unstructured":"R. M. Karp and R. J. Lipton. Turing machines that take advice. L'Enseignement Math\u00e9matique, 28:191\u2013209, 1982.","journal-title":"L'Enseignement Math\u00e9matique"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"S. Lindell. A constant-space sequential model of computation for first-order logic. Unpublished, 1995.","DOI":"10.1007\/3-540-60178-3_97"},{"issue":"2","key":"30_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0890-5401(90)90046-K","volume":"85","author":"C. Meinel","year":"1990","unstructured":"C. Meinel. Polynomial size \u03c9-branching programs and their computational power. Information and Computation, 85(2):163\u2013182, April 1990.","journal-title":"Information and Computation"},{"issue":"l","key":"30_CR9","first-page":"67","volume":"14","author":"B. Monien","year":"1980","unstructured":"B. Monien. Two-way multihead automata over a one-letter alphabet. R.A.I.R.O Informatique the\u00f2rique \/ Theoretical Informatics, 14(l):67\u201382, 1980.","journal-title":"R.A.I.R.O Informatique the\u00f2rique \/ Theoretical Informatics"},{"key":"30_CR10","unstructured":"P. Pudl\u00e1k and S. \u017dak. Space complexity of computations. Preprint, Charles University Prague, 1983."},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"W. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22:365\u2013338, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR12","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"I. H. Sudborough","year":"1975","unstructured":"I. H. Sudborough. On tape-bounded complexity classes and multihead finite automata. Journal of Computer and System Sciences, 10:62\u201376, 1975.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1997"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029973","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:22:18Z","timestamp":1586593338000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029973"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540634379","9783540695479"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0029973","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}