{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:49Z","timestamp":1725662869436},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108436"},{"type":"electronic","value":"9783540387459"}],"license":[{"start":{"date-parts":[[1981,1,1]],"date-time":"1981-01-01T00:00:00Z","timestamp":347155200000},"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":[[1981]]},"DOI":"10.1007\/3-540-10843-2_40","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:28:46Z","timestamp":1330190926000},"page":"506-520","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Alternating multihead finite automata"],"prefix":"10.1007","author":[{"given":"K. N.","family":"King","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer, Alternation, JACM 28 (1981), 114\u2013133.","journal-title":"JACM"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"A. K. Chandra and L. J. Stockmeyer, Alternation, Conf. Rec. IEEE 17th Ann. Symp. on Found. of Comp. Sci. (1976), 98\u2013108.","DOI":"10.1109\/SFCS.1976.4"},{"key":"40_CR3","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, JACM 18 (1971), 4\u201318.","journal-title":"JACM"},{"key":"40_CR4","volume-title":"Information Processing 71","author":"S. A. Cook","year":"1972","unstructured":"S. A. Cook, Linear time simulation of deterministic two-way pushdown automata, in Information Processing 71, North-Holland, Amsterdam (1972)."},{"key":"40_CR5","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S. A. Cook","year":"1974","unstructured":"S. A. Cook, An observation on time-space trade-off, J. Comput. Sys. Sci. 9 (1974), 308\u2013316.","journal-title":"J. Comput. Sys. Sci."},{"key":"40_CR6","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF01683273","volume":"10","author":"Z. Galil","year":"1977","unstructured":"Z. Galil, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, Math. Systems Theory 10 (1977), 211\u2013228.","journal-title":"Math. Systems Theory"},{"key":"40_CR7","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/S0019-9958(68)90901-7","volume":"13","author":"M. A. Harrison","year":"1968","unstructured":"M. A. Harrison and O. H. Ibarra, Multi-tape and multi-head pushdown automata, Inform. Control 13 (1968), 433\u2013470.","journal-title":"Inform. Control"},{"key":"40_CR8","doi-asserted-by":"crossref","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 Inform. 1 (1972), 336\u2013344.","journal-title":"Acta Inform."},{"key":"40_CR9","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/S0022-0000(73)80048-0","volume":"7","author":"O. H. Ibarra","year":"1973","unstructured":"O. H. Ibarra, On two-way multihead automata, J. Comput. Sys. Sci. 7 (1973), 28\u201336.","journal-title":"J. Comput. Sys. Sci."},{"key":"40_CR10","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. D. Jones","year":"1975","unstructured":"N. D. Jones, Space-bounded reducibility among combinatorial problems, J. Comput. Sys. Sci. 11 (1975), 68\u201385.","journal-title":"J. Comput. Sys. Sci."},{"key":"40_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. D. Jones","year":"1977","unstructured":"N. D. Jones and W. T. Laaser, Complete problems for deterministic polynomial time, Theoretical Computer Science 3 (1977), 105\u2013117.","journal-title":"Theoretical Computer Science"},{"key":"40_CR12","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/S0022-0000(72)80019-9","volume":"6","author":"T. Kameda","year":"1972","unstructured":"T. Kameda, Pushdown automata with counters, J. Comput. Sys. Sci. 6 (1972), 138\u2013150.","journal-title":"J. Comput. Sys. Sci."},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"D. Kozen, On parallelism in Turing machines, Conf. Rec. IEEE 17th Ann. Symp. on Found. of Comp. Sci. (1976), 89\u201397.","DOI":"10.1109\/SFCS.1976.20"},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"R. E. Ladner, R. J. Lipton, and L. J. Stockmeyer, Alternating pushdown automata, Conf. Rec. IEEE 19th Ann. Symp. on Found. of Comp. Sci. (1978), 92\u2013106.","DOI":"10.1109\/SFCS.1978.6"},{"key":"40_CR15","doi-asserted-by":"crossref","unstructured":"B. Monien, Characterizations of time-bounded computations by limited primitive recursion, Second Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science 14, Springer-Verlag (1974), 280\u2013293.","DOI":"10.1007\/978-3-662-21545-6_20"},{"key":"40_CR16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF00263746","volume":"6","author":"B. Monien","year":"1976","unstructured":"B. Monien, Transformational methods and their application to complexity problems, Acta Inform. 6 (1976), 95\u2013108. Corrigendum, Acta Inform. 8 (1977), 383\u2013384.","journal-title":"Acta Inform."},{"key":"40_CR17","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1051\/ita\/1980140100671","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 th\u00e9orique 14 (1980), 67\u201382.","journal-title":"R.A.I.R.O. Informatique th\u00e9orique"},{"key":"40_CR18","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/B978-0-12-115350-2.50015-4","volume-title":"Formal Language Theory: Perspectives and Open Problems","author":"B. Monien","year":"1980","unstructured":"B. Monien and I. H. Sudborough, The interface between language theory and complexity theory, in \u2018Formal Language Theory: Perspectives and Open Problems,\u2019 R. V. Book, ed., Academic Press, New York, 1980, pp. 287\u2013323."},{"key":"40_CR19","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0022-0000(77)80041-X","volume":"14","author":"J. I. Seiferas","year":"1977","unstructured":"J. I. Seiferas, Techniques for separating space complexity classes, J. Comput. Sys. Sci. 14 (1977), 73\u201399.","journal-title":"J. Comput. Sys. Sci."},{"key":"40_CR20","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0022-0000(77)80042-1","volume":"14","author":"J. I. Seiferas","year":"1977","unstructured":"J. I. Seiferas, Relating refined space complexity classes, J. Comput. Sys. Sci. 14 (1977), 100\u2013129.","journal-title":"J. Comput. Sys. Sci."},{"key":"40_CR21","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, J. Comput. Sys. Sci. 10 (1975), 62\u201376.","journal-title":"J. Comput. Sys. Sci."},{"key":"40_CR22","doi-asserted-by":"crossref","unstructured":"I. H. Sudborough, On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store, Proc. 8th Ann. Symp. on Theory of Computing (1976), 141\u2013148.","DOI":"10.1145\/800113.803642"},{"key":"40_CR23","doi-asserted-by":"crossref","unstructured":"I. H. Sudborough, Separating tape bounded auxiliary pushdown automata classes, Proc. 9th Ann. Symp. on Theory of Computing (1977), 208\u2013217.","DOI":"10.1145\/800105.803410"},{"key":"40_CR24","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1051\/ita\/1977110301811","volume":"11","author":"I. H. Sudborough","year":"1977","unstructured":"I. H. Sudborough, Some remarks on multihead automata, R.A.I.R.O. Informatique th\u00e9orique 11 (1977), 181\u2013195.","journal-title":"R.A.I.R.O. Informatique th\u00e9orique"},{"key":"40_CR25","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/322063.322076","volume":"25","author":"A. C. Yao","year":"1978","unstructured":"A. C. Yao and R. L. Rivest, k + 1 heads are better than k, JACM 25 (1978), 337\u2013340.","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10843-2_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:15:22Z","timestamp":1578525322000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10843-2_40"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108436","9783540387459"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-10843-2_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]},"assertion":[{"value":"25 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}