{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:25:33Z","timestamp":1774589133883,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642283314","type":"print"},{"value":"9783642283321","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28332-1_23","type":"book-chapter","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T14:45:36Z","timestamp":1330526736000},"page":"264-276","source":"Crossref","is-referenced-by-count":4,"title":["Two-Way Automata Making Choices Only at the Endmarkers"],"prefix":"10.1007","author":[{"given":"Viliam","family":"Geffert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Guillon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Pighizzini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-10003-2_62","volume-title":"Automata, Languages and Programming","author":"P. Berman","year":"1980","unstructured":"Berman, P.: A note on Sweeping Automata. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol.\u00a085, pp. 91\u201397. Springer, Heidelberg (1980)"},{"key":"23_CR2","unstructured":"Berman, P., Lingas, A.: On the complexity of regular languages in terms of finite automata. Tech. Rep. 304, Polish Academy of Sciences (1977)"},{"issue":"1","key":"23_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., Stockmeyer, L.J.: Alternation. J. ACM\u00a028(1), 114\u2013133 (1981)","journal-title":"J. ACM"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoretical Computer Science\u00a047, 149\u2013158 (1986); Errata: ibid 302, 497\u2013498","journal-title":"Theoretical Computer Science"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BFb0023453","volume-title":"STACS 97","author":"P. Duris","year":"1997","unstructured":"Duris, P., Hromkovi\u010d, J., Rolim, J.D.P., Schnitger, G.: Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, pp. 117\u2013128. Springer, Heidelberg (1997)"},{"key":"23_CR6","unstructured":"Geffert, V.: An alternating hierarchy for finite automata. In: Non-Classical Models of Automata and Applications (NCMA 2011), pp. 15\u201336 (2011)"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(02)00403-6","volume":"295","author":"V. Geffert","year":"2003","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theor. Comput. Sci.\u00a0295, 189\u2013203 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"23_CR8","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1016\/j.ic.2007.01.008","volume":"205","author":"V. Geffert","year":"2007","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Inf. Comput.\u00a0205(8), 1173\u20131187 (2007)","journal-title":"Inf. Comput."},{"issue":"7","key":"23_CR9","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.1016\/j.ic.2011.03.003","volume":"209","author":"V. Geffert","year":"2011","unstructured":"Geffert, V., Pighizzini, G.: Two-way unary automata versus logarithmic space. Inf. Comput.\u00a0209(7), 1016\u20131025 (2011)","journal-title":"Inf. Comput."},{"key":"23_CR10","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)"},{"key":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/3-540-45061-0_36","volume-title":"Automata, Languages and Programming","author":"J. Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Nondeterminism Versus Determinism for Two-way Finite Automata: Generalizations of Sipser\u2019s Separation. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 439\u2013451. Springer, Heidelberg (2003)"},{"issue":"3","key":"23_CR12","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","volume":"22","author":"N. Immerman","year":"1981","unstructured":"Immerman, N.: Number of quantifiers is better than number of tape cells. Journal of Computer and System Sciences\u00a022(3), 384\u2013406 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"23_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/11786986_14","volume-title":"Automata, Languages and Programming","author":"C.A. Kapoutsis","year":"2006","unstructured":"Kapoutsis, C.A.: Small Sweeping 2NFAs Are Not Closed Under Complement. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part I. LNCS, vol.\u00a04051, pp. 144\u2013156. Springer, Heidelberg (2006)"},{"key":"23_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-02737-6_4","volume-title":"Developments in Language Theory","author":"C.A. Kapoutsis","year":"2009","unstructured":"Kapoutsis, C.A.: Size Complexity of Two-Way Finite Automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol.\u00a05583, pp. 47\u201366. Springer, Heidelberg (2009)"},{"key":"23_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-642-22012-8_15","volume-title":"Automata, Languages and Programming","author":"C.A. Kapoutsis","year":"2011","unstructured":"Kapoutsis, C.A.: Nondeterminism Is Essential in Small 2FAs with Few Reversals. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 198\u2013209. Springer, Heidelberg (2011)"},{"key":"23_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-642-20712-9_28","volume-title":"Computer Science \u2013 Theory and Applications","author":"C.A. Kapoutsis","year":"2011","unstructured":"Kapoutsis, C.A.: Two-Way Automata versus Logarithmic Space. In: Kulikov, A.S., Vereshchagin, N.K. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 359\u2013372. Springer, Heidelberg (2011)"},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Kapoutsis, C.A., Pighizzini, G.: Two-way automata characterizations of L\/poly versus NL (2011) (submitted manuscript)","DOI":"10.1007\/978-3-642-30642-6_21"},{"issue":"2","key":"23_CR18","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0020-0190(81)90012-0","volume":"12","author":"S. Micali","year":"1981","unstructured":"Micali, S.: Two-way deterministic finite automata are exponentially more succinct than sweeping automata. Information Processing Letters\u00a012(2), 103\u2013105 (1981)","journal-title":"Information Processing Letters"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: STOC, pp. 275\u2013286. ACM (1978)","DOI":"10.1145\/800133.804357"},{"issue":"2","key":"23_CR20","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci.\u00a04(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M. Sipser","year":"1980","unstructured":"Sipser, M.: Halting space-bounded computations. Theor. Comput. Sci.\u00a010, 335\u2013338 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"23_CR22","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M. Sipser","year":"1980","unstructured":"Sipser, M.: Lower bounds on the size of sweeping automata. J. Comput. Syst. Sci.\u00a021(2), 195\u2013202 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR23","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)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28332-1_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T08:30:49Z","timestamp":1556440249000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28332-1_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642283314","9783642283321"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28332-1_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}