{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T01:10:38Z","timestamp":1772068238848,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540662242","type":"print"},{"value":"9783540485230","type":"electronic"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48523-6_40","type":"book-chapter","created":{"date-parts":[[2007,12,10]],"date-time":"2007-12-10T12:06:31Z","timestamp":1197288391000},"page":"433-442","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On the Power of Las Vegas II. Two-Way Finite Automata"],"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":[[2002,1,18]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Aho, A.V., Hopcroft, J.E., Yannakakis, M.: On notions of information transfer in VLSI circuits. In: Proc. 15th Annual ACM STOCS, ACM1983, pp. 133\u2013139.","DOI":"10.1145\/800061.808742"},{"key":"40_CR2","unstructured":"Babai, L.: Monte Carlo algorithms in graph isomorphism techniques. Research Report no. 79-10, D\u00e9partement de math\u00e9matiques et statistique, Universit\u00e9 de Montr\u00e9al 1979."},{"key":"40_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/3-540-10003-2_62","volume-title":"Proc. of 7th ICALP\u2019 80","author":"P. Berman","year":"1980","unstructured":"Berman, P.: A note on sweeping automata. In Proc. of 7th ICALP\u2019 80 (J.W. de Bakker and Jan van Leeuwen, editors), Lecture Notes in Computer Science 85, 1980, pp. 91\u201397."},{"key":"40_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BFb0023453","volume-title":"Proc. STACS\u2019 97","author":"P. \u010euri\u0161","year":"1997","unstructured":"\u010euri\u0161, 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: Proc. STACS\u2019 97, Lecture Notes in Computer Science 1200, Springer 1997, pp. 117\u2013128 (extended version submitted to Information and Computation)."},{"key":"40_CR5","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0022-0000(05)80003-0","volume":"48","author":"M. Dietzelfelbinger","year":"1994","unstructured":"Dietzelfelbinger, M., Kutylowski, M., Reischuk, R.: Exact lower bounds for computing Boolean functions on CREW PRAMs. J. Computer System Sciences 48 (1994), pp. 231\u2013254.","journal-title":"J. Computer System Sciences"},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"G. J","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), pp. 675\u2013695.","journal-title":"SIAM J. Comput."},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J.: Communication Complexity and Parallel Computing. Springer-Verlag 1997.","DOI":"10.1007\/978-3-662-03442-2"},{"key":"40_CR8","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computations. Addison-Wesley, 1979."},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity, Cambridge University Press 1997.","DOI":"10.1017\/CBO9780511574948"},{"issue":"2","key":"40_CR10","doi-asserted-by":"publisher","first-page":"103105","DOI":"10.1016\/0020-0190(81)90012-0","volume":"12","author":"S. Micali","year":"1981","unstructured":"Micali, S.: Two-way deterministic_nite automata are exponentially more succinct than sweeping automata. Information Processing Letters, 12(2), 1981, pp. 103105","journal-title":"Information Processing Letters"},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Schmidt, E.: Las Vegas is better than determinism in VLSI and distributed computing. In: Proc. 14th ACM STOC\u201982, ACM 1982, pp. 330\u2013337.","DOI":"10.1145\/800070.802208"},{"key":"40_CR12","unstructured":"Macarie, I.I., Seiferas, J.I.: Strong equivalence of nondeterministic and randomized space-bounded computations. Manuscript."},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Papadimitrou, Ch., Sipser, M.: Communication complexity. J. Computer System Sciences 28, pp. 260\u2013269","DOI":"10.1016\/0022-0000(84)90069-2"},{"key":"40_CR14","unstructured":"Sauerhoff, M.: On nondeterminism versus randomness for read-once branching programs. Electronic Colloquium on Computational Complexity, TR 97-030."},{"key":"40_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/3-540-49116-3_46","volume-title":"Proc. STACS\u2019 99","author":"M. Sauerhoff","year":"1999","unstructured":"Sauerhoff, M.: On the size of randomized OBDDs and read-once branching programs for k-stable functions. In: Proc. STACS\u2019 99, Lecture Notes in Computer Science, 1563, Springer 1999, pp. 488\u2013499."},{"key":"40_CR16","doi-asserted-by":"crossref","unstructured":"Sipser, M.: Lower bounds on the size of sweeping automata. In: Proc. 11th ACM STOC, 1979, pp. 360\u2013364.","DOI":"10.1145\/800135.804429"},{"key":"40_CR17","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. of Computer and System Sciences 21 (1980), pp. 195\u2013202.","journal-title":"J. of Computer and System Sciences"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: Proc. of 10th ACM STOC, ACM 1978, pp. 275\u2013286.","DOI":"10.1145\/800133.804357"},{"key":"40_CR19","series-title":"Wiley-Teubner Series in Computer Science","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, John Wiley and Sons Ltd., and Teubner, B.G., Stuttgart 1987."},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Some complexity questions related to distributed computing. In: Proc. 11th ACM STOC, ACM 1979, pp. 209\u2013213.","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48523-6_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T03:08:18Z","timestamp":1642820898000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48523-6_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662242","9783540485230"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-48523-6_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"18 January 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}