{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:14Z","timestamp":1725483734313},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_55","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"599-608","source":"Crossref","is-referenced-by-count":0,"title":["Unary Pushdown Automata and Auxiliary Space Lower Bounds"],"prefix":"10.1007","author":[{"given":"Giovanni","family":"Pighizzini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"55_CR1","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proc. FCT\u2019 85","author":"M. Alberts","year":"1985","unstructured":"M. Alberts. Space complexity of alternating Turing machines. In Proc. FCT\u2019 85, Lecture Notes in Computer Science 199, pages 1\u20137. Springer Verlag, 1985."},{"key":"55_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/3-540-60246-1_137","volume-title":"Proc. MFCS\u2019 95","author":"A. Bertoni","year":"1995","unstructured":"A. Bertoni, C. Mereghetti, and G. Pighizzini. Strong optimal lower bounds for Turing machines that accept nonregular languages. In Proc. MFCS\u2019 95, Lecture Notes in Computer Science 969, pages 309\u2013318. Springer Verlag, 1995."},{"key":"55_CR3","series-title":"Lect Notes Comput Sci","first-page":"133","volume-title":"Proc. 3rd GI Conference","author":"F. Brandenburg","year":"1977","unstructured":"F. Brandenburg. On one-way auxiliary pushdown automata. In Proc. 3rd GI Conference, Lecture Notes in Computer Science 48, pages 133\u2013144, 1977."},{"key":"55_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"M. Chrobak. Finite automata and unary languages. Theoretical Computer Science, 47:149\u2013158, 1986.","journal-title":"Theoretical Computer Science"},{"key":"55_CR5","doi-asserted-by":"crossref","first-page":"283","DOI":"10.3233\/FI-1986-9303","volume":"IX","author":"M. Chytil","year":"1986","unstructured":"M. Chytil. Almost context-free languages. Fundamenta Inform., IX:283\u2013322, 1986.","journal-title":"Fundamenta Inform."},{"key":"55_CR6","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1137\/0222009","volume":"22","author":"V. Geffert","year":"1993","unstructured":"V. Geffert. Tally version of the Savitch and Immerman-Szelepcs\u00e9nyi theorems for sublogarithmic space. SIAM J. Computing, 22:102\u2013113, 1993.","journal-title":"SIAM J. Computing"},{"key":"55_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/3-540-60246-1_112","volume-title":"Proc. MFCS\u2019 95","author":"V. Geffert","year":"1995","unstructured":"V. Geffert. Bridging across the log(n) space frontier. In Proc. MFCS\u2019 95, Lecture Notes in Computer Science 969, pages 50\u201365. Springer Verlag, 1995. To appear in Information and Computation."},{"issue":"1","key":"55_CR8","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1137\/S0097539796301306","volume":"28","author":"V. Geffert","year":"1999","unstructured":"V. Geffert, C. Mereghetti, and G. Pighizzini. Sublogarithmic bounds on space and reversals. SIAM J. Computing, 28(1):325\u2013340, 1999.","journal-title":"SIAM J. Computing"},{"issue":"3","key":"55_CR9","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/321127.321132","volume":"9","author":"S. Ginsburg","year":"1962","unstructured":"S. Ginsburg and H. Rice. Two families of languages related to ALGOL. Journal of the ACM, 9(3):350\u2013371, 1962.","journal-title":"Journal of the ACM"},{"key":"55_CR10","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0304-3975(82)90110-4","volume":"18","author":"J. Goldstine","year":"1982","unstructured":"J. Goldstine, J. Price, and D. Wotschke. A pushdown automaton or a context-free grammar \u2014 which is more economical? Theoretical Comp. Sc., 18:33\u201340, 1982.","journal-title":"Theoretical Comp. Sc."},{"key":"55_CR11","unstructured":"J. Gruska. Descriptional complexity of context-free languages. In Proc. MFCS\u2019 73, pages 71\u201383. Mathematical Institute of the Slovak Academy of Sciences, 1973."},{"key":"55_CR12","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321495.321508","volume":"16","author":"J. Hopcroft","year":"1969","unstructured":"J. Hopcroft and J. Ullman. Some results on tape-bounded Turing machines. Journal of the ACM, 16:168\u2013177, 1969.","journal-title":"Journal of the ACM"},{"key":"55_CR13","volume-title":"Introduction to automata theory, languages, and computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, Reading, MA, 1979."},{"key":"55_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/3-540-54458-5_73","volume-title":"Proc. FCT\u2019 91","author":"J. Ka\u0146eps","year":"1991","unstructured":"J. Ka\u0146eps. Regularity of one-letter languages acceptable by 2-way finite probabilistic automata. In Proc. FCT\u2019 91, Lecture Notes in Computer Science 529, pages 287\u2013296. Springer Verlag, 1991."},{"issue":"3","key":"55_CR15","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1145\/321406.321410","volume":"14","author":"R.M. Karp","year":"1967","unstructured":"R.M. Karp. Some bounds on the storage requirements of sequential machines and Turing machines. Journal of the ACM, 14(3):478\u2013489, 1967.","journal-title":"Journal of the ACM"},{"key":"55_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BFb0028556","volume-title":"Proc. STACS\u2019 98","author":"C. Mereghetti","year":"1998","unstructured":"C. Mereghetti and G. Pighizzini. Optimal simulations between unary automata. In Proc. STACS\u2019 98, Lecture Notes in Computer Science 1373, pages 139\u2013149. Springer, 1998."},{"issue":"1","key":"55_CR17","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1006\/jcss.1996.0046","volume":"53","author":"J. Shallit","year":"1996","unstructured":"J. Shallit and Y. Breitbart. Automaticity I: Properties of a measure of descriptional complexity. J. Comp. and System Sciences, 53(1):10\u201325, 1996.","journal-title":"J. Comp. and System Sciences"},{"key":"55_CR18","doi-asserted-by":"crossref","unstructured":"R. Stearns, J. Hartmanis, and P. Lewis. Hierarchies of memory limited computations. In IEEE Conf. Record on Switching Circuit Theory and Logical Design, pages 179\u2013190, 1965.","DOI":"10.1109\/FOCS.1965.11"},{"key":"55_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-58355-6","volume-title":"Turing Machines with Sublogarithmic Space","author":"A. Szepietowski","year":"1994","unstructured":"A. Szepietowski. Turing Machines with Sublogarithmic Space. Lecture Notes in Computer Science 843. Springer Verlag, 1994."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,13]],"date-time":"2021-08-13T04:24:33Z","timestamp":1628828673000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_55","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}