{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:26Z","timestamp":1759638926779,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319983547"},{"type":"electronic","value":"9783319983554"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98355-4_8","type":"book-chapter","created":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T10:34:57Z","timestamp":1533724497000},"page":"113-126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Probabilism versus Alternation for Automata"],"prefix":"10.1007","author":[{"given":"Georg","family":"Schnitger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"issue":"4","key":"8_CR1","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"DA Barrington","year":"1988","unstructured":"Barrington, D.A., Th\u00e9rien, D.: Finite monoids and the fine structure of NC$$^1$$. J. ACM 35(4), 941\u2013952 (1988)","journal-title":"J. ACM"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0020-0190(96)00016-6","volume":"57","author":"R Canetti","year":"1996","unstructured":"Canetti, R.: More on BPP and the polynomial-time hierarchy. Inf. Process. Lett. 57, 237\u2013241 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"8_CR3","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"AK Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114\u2013133 (1981)","journal-title":"J. ACM"},{"issue":"1","key":"8_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ic.2004.05.002","volume":"194","author":"P D\u030curi\u0161","year":"2004","unstructured":"D\u030curi\u0161, P., Hromkovi\u010d, J., Jukna, S., Sauerhoff, M., Schnitger, G.: On multi-partition communication complexity. Inf. Comput. 194(1), 49\u201375 (2004)","journal-title":"Inf. Comput."},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0304-3975(96)00062-X","volume":"168","author":"M Dietzfelbinger","year":"1996","unstructured":"Dietzfelbinger, M., Hromkovi\u010d, J., Schnitger, G.: A comparison of two lower-bound methods for communication complexity. Theor. Comput. Sci. 168(1), 39\u201351 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.044","volume":"445","author":"V Geffert","year":"2012","unstructured":"Geffert, V.: An alternating hierarchy for finite automata. Theor. Comput. Sci. 445, 1\u201324 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: STOC, pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"issue":"2","key":"8_CR8","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/inco.2001.3069","volume":"172","author":"J Hromkovi\u010d","year":"2002","unstructured":"Hromkovi\u010d, J., Seibert, S., Karhum\u00e4ki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Inf. Comput. 172(2), 202\u2013217 (2002)","journal-title":"Inf. Comput."},{"issue":"2","key":"8_CR9","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1006\/inco.2001.3040","volume":"169","author":"J Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inf. Comput. 169(2), 284\u2013296 (2001)","journal-title":"Inf. Comput."},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1137\/S0097539702414622","volume":"33","author":"J Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Nondeterministic communication with a limited number of advice bits. SIAM J. Comput. 33(1), 43\u201368 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"8_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.tcs.2007.02.063","volume":"380","author":"J Hromkovi\u010d","year":"2007","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Comparing the size of NFAs with and without epsilon-transitions. Theor. Comput. Sci. 380(1\u20132), 100\u2013114 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"30\u201332","key":"8_CR12","doi-asserted-by":"publisher","first-page":"2972","DOI":"10.1016\/j.tcs.2009.03.020","volume":"410","author":"J Hromkovi\u010d","year":"2009","unstructured":"Hromkovi\u010d, J., Petersen, H., Schnitger, G.: On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA\u2019s. Theor. Comput. Sci. 410(30\u201332), 2972\u20132981 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"8_CR13","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s00224-010-9277-4","volume":"48","author":"J Hromkovi\u010d","year":"2011","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Ambiguity and communication. Theory Comput. Syst. 48(3), 517\u2013534 (2011)","journal-title":"Theory Comput. Syst."},{"key":"8_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":"CA Kapoutsis","year":"2009","unstructured":"Kapoutsis, C.A.: Size complexity of two-way finite automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 47\u201366. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02737-6_4"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C Lautemann","year":"1983","unstructured":"Lautemann, C.: BPP and the polynomial hierarchy. Inf. Process. Lett. 17, 215\u2013217 (1983)","journal-title":"Inf. Process. Lett."},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: ACM Symposium on Theoretical Computer Science, pp. 330\u2013335 (1983)","DOI":"10.1145\/800061.808762"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds. In: IEEE Conference on Computational Complexity, pp. 115\u2013125 (2011)","DOI":"10.1109\/CCC.2011.36"}],"container-title":["Lecture Notes in Computer Science","Adventures Between Lower Bounds and Higher Altitudes"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98355-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:55:26Z","timestamp":1710348926000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-98355-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319983547","9783319983554"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98355-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"9 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}