{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T08:10:07Z","timestamp":1746346207728,"version":"3.40.4"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319096971"},{"type":"electronic","value":"9783319096988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09698-8_28","type":"book-chapter","created":{"date-parts":[[2014,8,18]],"date-time":"2014-08-18T00:52:51Z","timestamp":1408323171000},"page":"315-326","source":"Crossref","is-referenced-by-count":1,"title":["The Minimum Amount of Useful Space: New Results and New Directions"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Reinhardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abuzer","family":"Yakary\u0131lmaz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Amano, M., Iwama, K.: Undecidability on quantum finite automata. In: STOC 1999: Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, pp. 368\u2013375 (1999)","DOI":"10.1145\/301250.301344"},{"issue":"1","key":"28_CR2","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0304-3975(02)00138-X","volume":"287","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A., Watrous, J.: Two\u2013way finite automata with quantum and classical states. Theoretical Computer Science\u00a0287(1), 299\u2013311 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. Journal of the ACM\u00a028(1), 114\u2013133 (1981)","journal-title":"Journal of the ACM"},{"key":"28_CR4","unstructured":"\u010euri\u0161, P.: Private communication (October 2013)"},{"issue":"3","key":"28_CR5","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0019-9958(82)80023-5","volume":"54","author":"P. \u010euri\u0161","year":"1982","unstructured":"\u010euri\u0161, P., Galil, Z.: On reversal-bounded counter machines and on pushdown automata with a bound on the size of their pushdown store. Information and Control\u00a054(3), 217\u2013227 (1982)","journal-title":"Information and Control"},{"issue":"6","key":"28_CR6","doi-asserted-by":"publisher","first-page":"1011","DOI":"10.1137\/0219069","volume":"19","author":"C. Dwork","year":"1990","unstructured":"Dwork, C., Stockmeyer, L.: A time complexity gap for two-way probabilistic finite-state automata. SIAM Journal on Computing\u00a019(6), 1011\u20131123 (1990)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"Freivalds, R.: Probabilistic two-way machines. In: Gruska, J., Chytil, M.P. (eds.) MFCS 1981. LNCS, vol.\u00a0118, pp. 33\u201345. Springer, Heidelberg (1981)","DOI":"10.1007\/3-540-10856-4_72"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Freivalds, R.: Space and reversal complexity of probabilistic one-way Turing machines. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol.\u00a0158, pp. 159\u2013170. Springer, Heidelberg (1983)","DOI":"10.1007\/3-540-12689-9_101"},{"key":"28_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/3-540-58201-0_100","volume-title":"Automata, Languages, and Programming","author":"R. Freivalds","year":"1994","unstructured":"Freivalds, R., Karpinski, M.: Lower space bounds for randomized computation. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol.\u00a0820, pp. 580\u2013592. Springer, Heidelberg (1994)"},{"key":"28_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/3-540-12920-0_23","volume-title":"STACS 84","author":"J. Gabarr\u00f3","year":"1984","unstructured":"Gabarr\u00f3, J.: Pushdown space complexity and related full-A.F.L.s. In: Fontet, M., Mehlhorn, K. (eds.) STACS 1984. LNCS, vol.\u00a0166, pp. 250\u2013259. Springer, Heidelberg (1984)"},{"issue":"3","key":"28_CR11","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/321127.321132","volume":"9","author":"S. Ginsburg","year":"1962","unstructured":"Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL. Journal of the ACM\u00a09(3), 350\u2013371 (1962)","journal-title":"Journal of the ACM"},{"key":"28_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/3-540-54458-5_73","volume-title":"Fundamentals of Computation Theory","author":"J. Ka\u0146eps","year":"1991","unstructured":"Ka\u0146eps, J.: Regularity of one-letter languages acceptable by 2-way finite probabilistic automata. In: Budach, L. (ed.) FCT 1991. LNCS, vol.\u00a0529, pp. 287\u2013296. Springer, Heidelberg (1991)"},{"key":"28_CR13","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. Ka\u0146eps","year":"1990","unstructured":"Ka\u0146eps, 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":"28_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/3-540-63248-4_16","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"J. Ka\u0146eps","year":"1997","unstructured":"Ka\u0146eps, J., Geidmanis, D., Freivalds, R.: Tally languages accepted by Monte Carlo pushdown automata. In: Rolim, J.D.P. (ed.) RANDOM 1997. LNCS, vol.\u00a01269, pp. 187\u2013195. Springer, Heidelberg (1997)"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: FOCS 1997, pp. 66\u201375 (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"key":"28_CR16","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2000)"},{"key":"28_CR17","volume-title":"Introduction to Probabilistic Automata","author":"A. Paz","year":"1971","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)"},{"key":"28_CR18","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. Information and Control\u00a06, 230\u2013243 (1963)","journal-title":"Information and Control"},{"issue":"6","key":"28_CR19","doi-asserted-by":"publisher","first-page":"1383","DOI":"10.1142\/S012905410700542X","volume":"18","author":"K. Reinhardt","year":"2007","unstructured":"Reinhardt, K.: A tree-height hierarchy of context-free languages. International Journal of Foundations of Computer Science\u00a018(6), 1383\u20131394 (2007)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"28_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-58355-6","volume-title":"Turing Machines with Sublogarithmic Space","author":"A. Szepietowski","year":"1994","unstructured":"Szepietowski, A.: Turing Machines with Sublogarithmic Space. LNCS, vol.\u00a0843. Springer, Heidelberg (1994)"},{"issue":"4","key":"28_CR21","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1051\/ita\/2012018","volume":"46","author":"A. Yakary\u0131lmaz","year":"2012","unstructured":"Yakary\u0131lmaz, A.: Superiority of one-way and realtime quantum machines. RAIRO - Theoretical Informatics and Applications\u00a046(4), 615\u2013641 (2012)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"key":"28_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-642-38536-0_32","volume-title":"Computer Science \u2013 Theory and Applications","author":"A. Yakary\u0131lmaz","year":"2013","unstructured":"Yakary\u0131lmaz, A.: One-counter verifiers for decidable languages. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol.\u00a07913, pp. 366\u2013377. Springer, Heidelberg (2013)"},{"key":"28_CR23","unstructured":"Yakary\u0131lmaz, A.: Public qubits versus private coins. In: The Proceedings of Workshop on Quantum and Classical Complexity, pp. 45\u201360. Univeristy of Latvia Press (2013), ECCC:TR12-130"},{"issue":"20","key":"28_CR24","doi-asserted-by":"publisher","first-page":"1932","DOI":"10.1016\/j.tcs.2009.01.029","volume":"410","author":"A. Yakary\u0131lmaz","year":"2009","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Efficient probability amplification in two-way quantum finite automata. Theoretical Computer Science\u00a0410(20), 1932\u20131941 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"28_CR25","first-page":"19","volume":"12","author":"A. Yakary\u0131lmaz","year":"2010","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics and Theoretical Computer Science\u00a012(2), 19\u201340 (2010)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"issue":"8","key":"28_CR26","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1142\/S0129054113500329","volume":"24","author":"A. Yakary\u0131lmaz","year":"2013","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Tight bounds for the space complexity of nonregular language recognition by real-time machines. International Journal of Foundations of Computer Science\u00a024(8), 1243\u20131253 (2013)","journal-title":"International Journal of Foundations of Computer Science"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09698-8_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T07:38:22Z","timestamp":1746344302000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09698-8_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319096971","9783319096988"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09698-8_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}