{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:47:49Z","timestamp":1725468469957},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055779","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T13:36:31Z","timestamp":1155821791000},"page":"296-304","source":"Crossref","is-referenced-by-count":2,"title":["The head hierarchy for oblivious finite automata with polynomial advice collapses"],"prefix":"10.1007","author":[{"given":"Holger","family":"Petersen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"26_CR1","volume-title":"Structural Complexity I, volume 11 of EATCS Monographs on Theoretical Computer Science","author":"J. L. Balc\u00e1zar","year":"1988","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, Berlin-Heidelberg-New York, 1988."},{"key":"26_CR2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. A. Cook","year":"1971","unstructured":"S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the Association for Computing Machinery, 18:4\u201318, 1971.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"26_CR3","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":"26_CR4","first-page":"299","volume-title":"number 1295 in Lecture Notes in Computer Science","author":"M. Holzer","year":"1997","unstructured":"M. Holzer. Multi-head finite automata: Data-independent versus data-dependent computations. In I. Pr\u00edvara and P. Ru\u017di\u010dka, editors, Proceedings of the 22nd Symposium on Mathematical Foundations of Computer Science (MFCS), Bratislava, 1997, number 1295 in Lecture Notes in Computer Science, pages 299\u2013308. Springer, 1997."},{"key":"26_CR5","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":"26_CR6","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(88)90122-3","volume":"61","author":"K. N. King","year":"1988","unstructured":"K. N. King. Alternating multihead finite automata. Theoretical Computer Science, 61:149\u2013174, 1988.","journal-title":"Theoretical Computer Science"},{"key":"26_CR7","first-page":"124","volume":"21","author":"V. A. Kosmidiadi","year":"1971","unstructured":"V. A. Kosmidiadi and S. S. Marchenkov. On multihead automata. Systems Theory Research, 21:124\u2013156, 1971. Translation of Probl. Kib. 21:127\u2013158, 1969, in Russian.","journal-title":"Systems Theory Research"},{"key":"26_CR8","first-page":"18","volume":"7","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner. The Circuit Value Problem is log space complete for P. SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 7:18\u201320, 1975.","journal-title":"SIGACT News (ACM Special Interest Group on Automata and Computability Theory)"},{"key":"26_CR9","first-page":"280","volume-title":"number 14 in Lecture Notes in Computer Science","author":"B. Monien","year":"1974","unstructured":"B. Monien. Characterizations of time-bounded computations by limited primitive recursion. In Proceedings of the 2nd International Colloquium on Automata, Languages and Programming (ICALP), Saarbr\u00fccken, 1974, number 14 in Lecture Notes in Computer Science, pages 280\u2013293. Springer, 1974."},{"key":"26_CR10","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"},{"key":"26_CR11","volume-title":"Mathematics and its Applications","author":"K. Wagner","year":"1986","unstructured":"K. Wagner and G. Wechsung. Computational Complexity. Mathematics and its Applications. D. Reidel Publishing Company, Dordrecht, 1986."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T18:04:51Z","timestamp":1549908291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/bfb0055779","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}