{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:00Z","timestamp":1770994080103,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540404934","type":"print"},{"value":"9783540450610","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_36","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:04Z","timestamp":1184586844000},"page":"439-451","source":"Crossref","is-referenced-by-count":16,"title":["Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser\u2019s Separation"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"36_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/3-540-10003-2_62","volume-title":"Proc. 7th ICALP","author":"P. Berman","year":"1980","unstructured":"P. Berman: A note on sweeping automata. In: Proc. 7th ICALP. Lecture Notes in Computer Science 85, Springer 1980, pp. 91\u201397."},{"key":"36_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/3-540-44693-1_18","volume-title":"Proc. STACS\u2019 01","author":"P. \u010euri\u0161","year":"2001","unstructured":"P. \u010euri\u0161, J. Hromkovi\u010d, S. Jukna, M. Sauerhoff, G. Schnitger: On multipartition communication complexity. In: Proc. STACS\u2019 01. Lecture Notes in Computer Science 2010, Springer 2001, pp 206\u2013217."},{"key":"36_CR3","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d: Communication Complexity and Parallel Computing. Springer 1997.","DOI":"10.1007\/978-3-662-03442-2"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00155-9","volume":"262","author":"J. Hromkovi\u010d","year":"2001","unstructured":"J. Hromkovi\u010d, G. Schnitger: On the power of Las Vegas II: Two-way finite automata. Theoretical Computer Science 262 (2001), 1\u201324.","journal-title":"Theoretical Computer Science"},{"key":"36_CR5","series-title":"Lect Notes Comput Sci","first-page":"194","volume-title":"Proc. 27th ICALP","author":"J. Hromkovi\u010d","year":"2000","unstructured":"J. Hromkovi\u010d, J. Karhum\u00e4ki, H. Klauck, G. Schnitger, S. Seibert: Measures of nondeterminism in finite automata. In: Proc. 27th ICALP, Lecture Notes in Computer Science 1853, Springer-Verlag 2000, pp. 194\u201321, full version: Information and Computation 172 (2002), 202\u2013217."},{"issue":"3\u20134","key":"36_CR6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0016-0032(54)90574-8","volume":"257","author":"D. A. Huffman","year":"1954","unstructured":"D. A. Huffman: The synthesis of sequential switching circuits. J. Franklin Inst. 257, No. 3\u20134 (1954), pp. 161\u2013190 and pp. 257\u2013303.","journal-title":"J. Franklin Inst."},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"H. Leung: Tight lower bounds on the size of sweeping automata. J. Comp. System Sciences, to appear.","DOI":"10.1006\/jcss.2001.1783"},{"issue":"5","key":"36_CR8","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1002\/j.1538-7305.1955.tb03788.x","volume":"34","author":"G. M. Mealy","year":"1955","unstructured":"G. M. Mealy: A method for synthesizing sequential circuits. Bell System Technical Journal 34, No. 5 (1955), pp. 1045\u20131079.","journal-title":"Bell System Technical Journal"},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"A. Meyer and M. Fischer: Economy in description by automata, grammars and formal systems. In: Proc. 12th SWAT Symp., 1971, pp. 188\u2013191.","DOI":"10.1109\/SWAT.1971.11"},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0020-0190(81)90012-0","volume":"12","author":"S. Micali","year":"1981","unstructured":"S. Micali: Two-way deterministic automata are exponentially more succinct than sweeping automata. Inform. Proc. Letters 12 (1981), 103\u2013105.","journal-title":"Inform. Proc. Letters"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"E. F. Moore: Gedanken experiments on sequential machines. In: [14], pp. 129\u2013153.","DOI":"10.1515\/9781400882618-006"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"10","author":"F. Moore","year":"1971","unstructured":"F. Moore: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic and two-way finite automata. IEEE Trans. Comput. 10 (1971), 1211\u20131214.","journal-title":"IEEE Trans. Comput."},{"key":"36_CR13","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. O. Rabin","year":"1959","unstructured":"M. O. Rabin, D. Scott: Finite automata and their decision problems. In: IBM J. Research and Development, 3 (1959), pp. 115\u2013125.","journal-title":"IBM J. Research and Development"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"W. J. Sakoda, M. Sipser: Nondeterminism and the size of two-way finite automata. In: Proc. 10th ACM STOC, 1978, pp. 275\u2013286.","DOI":"10.1145\/800133.804357"},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"C. E. Shannon and J. McCarthy: Automata Studies. Princeton University Press, 1956.","DOI":"10.1515\/9781400882618"},{"key":"36_CR16","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M. Sipser","year":"1980","unstructured":"M. Sipser: Lower bounds on the size of sweeping automata. J. Comp. System Sciences 21 (1980), 195\u2013202.","journal-title":"J. Comp. System Sciences"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:13:35Z","timestamp":1556666015000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_36","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}