{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:48:23Z","timestamp":1725468503726},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"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":[[1998]]},"DOI":"10.1007\/bfb0055811","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T13:36:31Z","timestamp":1155821791000},"page":"607-615","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Speeding-up nondeterministic single-tape off-line computations by one alternation"],"prefix":"10.1007","author":[{"given":"Ji\u0159\u00ed","family":"Wiedermann","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"58_CR1","first-page":"602","volume":"6","author":"R.V. Book","year":"1970","unstructured":"Book, R.V.-Greibach, S.A.-Wegbreit, B.: Time-and Tape-Bounded Turing Acceptors and AFLs. JCSS 4, Vol. 6, Dec. 1970, pp. 602\u2013621","journal-title":"JCSS 4"},{"key":"58_CR2","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. Information and Control, Vol. 8, 1965, pp. 553\u2013578","journal-title":"Information and Control"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Dymond, P.W.-Tompa, M.: Speedups of Deterministic Machines by Synchronous Parallel Machines. In Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, pp. 336\u2013364, 1983","DOI":"10.1145\/800061.808763"},{"key":"58_CR4","unstructured":"Gupta, S.: Alternating Time Versus Deterministic Time: A Separation. Proc. of Structure in Complexity, San Diego, 1993"},{"key":"58_CR5","first-page":"57","volume":"16","author":"J. Hopcroft","year":"1975","unstructured":"Hopcroft, J.-Paul, W.-Valiant L.: On time versus space and related problems. Proc. IEEE FOCS\n                16, 1975, pp. 57\u201364","journal-title":"Proc. IEEE FOCS"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Kannan, R.: Alternation and the power of nondeterminism (Extended abstract). Proc. 15-th STOC, 1983, pp. 344\u2013346","DOI":"10.1145\/800061.808764"},{"key":"58_CR7","doi-asserted-by":"crossref","unstructured":"Lory\u015a, K.-Li\u015akiewicz, M.: Two Applications of F\u00fchrers Counter to One-Tape Nondeterministic TMs. Proceedings of the MFCS'88, LNCS Vol. 324, Springer Verlag, 1988, pp. 445\u2013453","DOI":"10.1007\/BFb0017167"},{"key":"58_CR8","doi-asserted-by":"publisher","first-page":"675","DOI":"10.2307\/2000238","volume":"292","author":"W. Maass","year":"1985","unstructured":"Maass, W.: Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines. Trans. Am. Math. Soc. 292, 1985, pp. 675\u2013693","journal-title":"Trans. Am. Math. Soc."},{"issue":"no.1","key":"58_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/0216016","volume":"16","author":"W. Maass","year":"1987","unstructured":"Maass, W.-Schorr, A.: Speed-up of Turing Machines with One Work Tape and Two-way Input Tape. SIAM J. Comput., Vol. 16, no. 1, 1987, pp. 195\u2013202","journal-title":"SIAM J. Comput."},{"key":"58_CR10","first-page":"116","volume":"6","author":"M. Paterson","year":"1972","unstructured":"Paterson, M.: Tape Bounds for Time-Bounded Turing Machines, JCSS, Vol. 6, 1972, pp. 116\u2013124","journal-title":"JCSS"},{"key":"58_CR11","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF00264255","volume":"14","author":"W. Paul","year":"1980","unstructured":"Paul, W.-Prauss, E. J.-Reischuk, R.: On Alternation. Acta Informatica, 14, 1980, pp. 243\u2013255","journal-title":"Acta Informatica"},{"key":"58_CR12","doi-asserted-by":"crossref","unstructured":"Paul, W.J.-Pippenger, N.-Szemer\u00e9di, E.-Trotter, W.T.: On determinism versus nondeterminism and related problems. In Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, pp. 429\u2013438, 1983","DOI":"10.1109\/SFCS.1983.39"},{"key":"58_CR13","volume-title":"LNCS Vol. 1099","author":"J. Wiedermann","year":"1996","unstructured":"Wiedermann, J.: Speeding-up Single-Tape Nondeterministic Computations by Single Alternation, with Separation Results. Proceedings of the 23-rd International Colloquium on Automata, Languages, and Programming, ICALP'96, LNCS Vol. 1099, Springer Verlag, Berlin, 1996"},{"key":"58_CR14","volume-title":"Technical Report V-725-97","author":"J. Wiedermann","year":"1998","unstructured":"Wiedermann, J.: Accelerating Nondeterministic Single-Tape Off-Line Computations by One Alternation. Technical Report V-725-97, Institute of Computer Science, Prague, 1998"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055811","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T14:48:23Z","timestamp":1578494903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055811"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/bfb0055811","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"28 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}