{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:33:33Z","timestamp":1725456813011},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633860"},{"type":"electronic","value":"9783540695295"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0036201","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T07:47:22Z","timestamp":1134287242000},"page":"400-410","source":"Crossref","is-referenced-by-count":1,"title":["The equivalence of pebbles and sensing heads for finite automata"],"prefix":"10.1007","author":[{"given":"Holger","family":"Petersen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,21]]},"reference":[{"key":"34_CR1","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0022-0000(92)90045-K","volume":"45","author":"J.-C. Birget","year":"1992","unstructured":"J.-C. Birget. Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations. Journal of Computer and System Sciences, 45:154\u2013179, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"M. Blum and C. Hewitt. Automata on a 2-dimensional tape. In Proceedings of the 8th Annual Symposium on Switching and Automata Theory, Austin, 1967, pages 155\u2013160, 1967.","DOI":"10.1109\/FOCS.1967.6"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(86)90112-X","volume":"44","author":"J. H. Chang","year":"1986","unstructured":"J. H. Chang, O. H. Marra, M. A. Palis, and B. Ravikumar. On pebble automata. Theoretical Computer Science, 44:111\u2013121, 1986.","journal-title":"Theoretical Computer Science"},{"key":"34_CR4","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0304-3975(82)90087-1","volume":"21","author":"P. \u010euri\u0161","year":"1982","unstructured":"P. \u010euri\u0161 and Z. Galil. Fooling a two way automaton or one pushdown store is better than one counter for two way machines. Theoretical Computer Science, 21:39\u201353, 1982.","journal-title":"Theoretical Computer Science"},{"key":"34_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/3-540-60084-1_96","volume-title":"Proceedings of the 22nd International Colloquium on Automata, Languages and Programming (ICALP), Szeged, 1995","author":"P. \u010euri\u0161","year":"1995","unstructured":"P. \u010euri\u0161 and Z. Galil. Sensing versus nonsensing automata. In Z. F\u00fcl\u00f6p and F. G\u00e9cseg, editors, Proceedings of the 22nd International Colloquium on Automata, Languages and Programming (ICALP), Szeged, 1995, number 944 in Lecture Notes in Computer Science, pages 455\u2013463, Berlin-Heidelberg-New York, 1995. Springer."},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0304-3975(96)00119-3","volume":"169","author":"N. Globerman","year":"1996","unstructured":"N. Globerman and D. Harel. Complexity results for two-way and multi-pebble automata and their logics, Theoretical Computer Science, 169:161\u2013184, 1996.","journal-title":"Theoretical Computer Science"},{"key":"34_CR7","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 Informatica, 1:336\u2013344, 1972.","journal-title":"Acta Informatica"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1142\/S0129054193000092","volume":"4","author":"O. H. Ibarra","year":"1993","unstructured":"O. H. Ibarra, T. Jiang, N. Tran, and H. Wang. On the equivalence of two-way pushdown automata and counter machines over bounded languages. International Journal of Foundations of Computer Science, 4:135\u2013146, 1993.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"34_CR9","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/S0019-9958(85)80029-2","volume":"67","author":"O. H. Ibarra","year":"1985","unstructured":"O. H. Ibarra, S. M. Kim, and L. E. Rosier. Some characterizations of multihead finite automata. Information and Control, 67:114\u2013125, 1985.","journal-title":"Information and Control"},{"key":"34_CR10","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-158, 1969, in Russian.","journal-title":"Systems Theory Research"},{"key":"34_CR11","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1002\/malq.19660120120","volume":"12","author":"D. L. Kreider","year":"1966","unstructured":"D. L. Kreider and R. W. Ritchie. A basis theorem for a class of two-way automata. Zeitschrift f\u00fcr mathematische Logik and Grundlagen der Mathematik, 12:243\u2013255, 1966.","journal-title":"Zeitschrift f\u00fcr mathematische Logik and Grundlagen der Mathematik"},{"key":"34_CR12","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. \u2014 Informatique Th\u00e9orique et Applications, 14:67\u201382, 1980.","journal-title":"R.A.I.R.O. \u2014 Informatique Th\u00e9orique et Applications"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"H. Petersen. Automata with sensing heads. In Proceedings of the Third Israel Symposium on the Theory of Computing and Systems, Tel Aviv, 1995, pages 150-157. IEEE Computer Society Press, 1995.","DOI":"10.1109\/ISTCS.1995.377036"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0019-9958(72)90205-7","volume":"20","author":"R. W. Ritchie","year":"1972","unstructured":"R. W. Ritchie and F. N. Springsteel. Language recognition by marking automata. Information and Control, 20:313\u2013330, 1972.","journal-title":"Information and Control"},{"key":"34_CR15","volume-title":"Picture Languages","author":"A. Rosenfeld","year":"1979","unstructured":"A. Rosenfeld. Picture Languages. Academic Press, New York, 1979."},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"W. J. Sakoda and M. Sipser. Nondeterminism and the size of two way finite automata. In Proceedings of the 10th ACM Symposium on Theory of Computing (STOC), San Diego, 1978, pages 275\u2013286, 1978.","DOI":"10.1145\/800133.804357"},{"key":"34_CR17","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J. C. Shepherdson","year":"1959","unstructured":"J. C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3:198\u2013200, 1959.","journal-title":"IBM Journal of Research and Development"},{"key":"34_CR18","first-page":"491","volume-title":"Proceedings of the 2nd Conference on Fundamentals of Computation Theory (FCT), Berlin\/Wendisch-Rietz, 1979","author":"L. Voelkel","year":"1979","unstructured":"L. Voelkel. Language recognition by linear bounded and copy programs. In Proceedings of the 2nd Conference on Fundamentals of Computation Theory (FCT), Berlin\/Wendisch-Rietz, 1979, pages 491\u2013495, Berlin, 1979. Akademie-Verlag."},{"key":"34_CR19","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","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0036201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,10]],"date-time":"2019-04-10T09:30:27Z","timestamp":1554888627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0036201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633860","9783540695295"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0036201","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}