{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:28:29Z","timestamp":1725564509512},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540207795"},{"type":"electronic","value":"9783540246183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24618-3_29","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T07:31:03Z","timestamp":1283671863000},"page":"335-348","source":"Crossref","is-referenced-by-count":4,"title":["Theory of One Tape Linear Time Turing Machines"],"prefix":"10.1007","author":[{"given":"Kohtaro","family":"Tadaki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomoyuki","family":"Yamakami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack C. H.","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"1524","DOI":"10.1137\/S0097539795293639","volume":"26","author":"L.M. Adleman","year":"1997","unstructured":"Adleman, L.M., DeMarrais, J., Huang, M.A.: Quantum Computability. SIAM J. Comput.\u00a026, 1524\u20131540 (1997)","journal-title":"SIAM J. Comput."},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"C.H. Bennett","year":"1973","unstructured":"Bennett, C.H.: Logical Reversibility of Computation. IBM J. Res. Develop.\u00a017, 525\u2013532 (1973)","journal-title":"IBM J. Res. Develop."},{"key":"29_CR3","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum Complexity Theory. SIAM J. Comput.\u00a026, 1411\u20131473 (1997)","journal-title":"SIAM J. Comput."},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1137\/S0097539799353443","volume":"31","author":"A. Brodsky","year":"2002","unstructured":"Brodsky, A., Pippenger, N.: Characterizations of 1-Way Quantum Finite Automata. SIAM J. Comput.\u00a031, 1456\u20131478 (2002)","journal-title":"SIAM J. Comput."},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/3-540-60246-1_121","volume-title":"Mathematical Foundations of Computer Science 1995","author":"C. Damm","year":"1995","unstructured":"Damm, C., Holzer, M.: Automata that Take Advice. In: H\u00e1jek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol.\u00a0969, pp. 149\u2013158. Springer, Heidelberg (1995)"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"1011","DOI":"10.1137\/0219069","volume":"19","author":"C. Dwork","year":"1990","unstructured":"Dwork, C., Stockmeyer, L.J.: A Time Complexity Gap for Two-Way Probabilistic Finite State Automata. SIAM J. Comput.\u00a019, 1011\u20131023 (1990)","journal-title":"SIAM J. Comput."},{"key":"29_CR7","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1145\/146585.146599","volume":"39","author":"C. Dwork","year":"1992","unstructured":"Dwork, C., Stockmeyer, L.: Finite State Verifiers I: The Power of Interaction. J. ACM\u00a039, 800\u2013828 (1992)","journal-title":"J. ACM"},{"key":"29_CR8","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"F.C. Hennie","year":"1965","unstructured":"Hennie, F.C.: One-Tape, Off-Line Turing Machine Computations. Inform. Control\u00a08, 553\u2013578 (1965)","journal-title":"Inform. Control"},{"key":"29_CR9","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1145\/321406.321410","volume":"14","author":"R.M. Karp","year":"1967","unstructured":"Karp, R.M.: Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines. J. ACM\u00a014, 478\u2013489 (1967)","journal-title":"J. ACM"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/BFb0029629","volume-title":"Mathematical Foundations of Computer Science 1990","author":"J. Kaneps","year":"1990","unstructured":"Kaneps, J., Freivalds, R.: Minimal Nontrivial Space Complexity of Probabilistic One-Way Turing Machines. In: Rovan, B. (ed.) MFCS 1990. LNCS, vol.\u00a0452, pp. 355\u2013361. Springer, Heidelberg (1990)"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(85)90165-3","volume":"40","author":"K. Kobayashi","year":"1985","unstructured":"Kobayashi, K.: On the Structure of One-Tape Nondeterministic Turing Machine Time Hierarchy. Theor. Comput. Sci.\u00a040, 175\u2013193 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the Power of Quantum Finite State Automata. In: Proc. 38th FOCS, pp. 66\u201375 (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/S0097539793253851","volume":"27","author":"I.I. Macarie","year":"1998","unstructured":"Macarie, I.I.: Space-Efficient Deterministic Simulation of Probabilistic Automata. SIAM J. Comput.\u00a027, 448\u2013465 (1998)","journal-title":"SIAM J. Comput."},{"key":"29_CR15","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(91)90054-6","volume":"85","author":"P. Michel","year":"1991","unstructured":"Michel, P.: An NP-Complete Language Accepted in Linear Time by a One-Tape Turing Machine. Theor. Comput. Sci.\u00a085, 205\u2013212 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic Automata. Inform. Control\u00a06, 230\u2013245 (1963)","journal-title":"Inform. Control"},{"key":"29_CR17","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/S0019-9958(68)90360-4","volume":"12","author":"P. Turakainen","year":"1968","unstructured":"Turakainen, P.: On Stochastic Languages. Inform. Control\u00a012, 304\u2013313 (1968)","journal-title":"Inform. Control"},{"key":"29_CR18","first-page":"4","volume":"439","author":"P. Turakainen","year":"1969","unstructured":"Turakainen, P.: On Languages Representable in Rational Probabilistic Automata. Annales Academiae Scientiarum Fennicae, Ser. A\u00a0439, 4\u201310 (1969)","journal-title":"Annales Academiae Scientiarum Fennicae, Ser. A"},{"key":"29_CR19","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1090\/S0002-9939-1969-0242596-1","volume":"21","author":"P. Turakainen","year":"1969","unstructured":"Turakainen, P.: Generalized Automata and Stochastic Languages. Proc. Amer. Math. Soc.\u00a021, 303\u2013309 (1969)","journal-title":"Proc. Amer. Math. Soc."},{"key":"29_CR20","unstructured":"Yamakami, T.: Average Case Complexity Theory. Ph.D. Dissertation, University of Toronto. Technical Report 307\/97, University of Toronto. See also ECCC Thesis Listings (1997)"},{"key":"29_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/3-540-48340-3_39","volume-title":"Mathematical Foundations of Computer Science 1999","author":"T. Yamakami","year":"1999","unstructured":"Yamakami, T.: A Foundation of Programming a Multi-Tape Quantum Turing Machine. In: Kuty\u0142owski, M., Wierzbicki, T., Pacholski, L. (eds.) MFCS 1999. LNCS, vol.\u00a01672, pp. 430\u2013441. Springer, Heidelberg (1999)"},{"key":"29_CR22","doi-asserted-by":"crossref","unstructured":"Yamakami, T.: Analysis of Quantum Functions. To appear in: International Journal of Foundations of Computer Science; A preliminary version appeared in: Pandu Rangan, C., Raman, V., Sarukkai, S. (eds.): FST TCS 1999. LNCS, vol.\u00a01738, pp. 407\u2013419. Springer, Heidelberg (1999)","DOI":"10.1007\/3-540-46691-6_33"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2004: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24618-3_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T15:09:11Z","timestamp":1548428951000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24618-3_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540207795","9783540246183"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24618-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}