{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T07:29:22Z","timestamp":1771745362427,"version":"3.50.1"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030625351","type":"print"},{"value":"9783030625368","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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":[[2020]]},"DOI":"10.1007\/978-3-030-62536-8_8","type":"book-chapter","created":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T02:02:50Z","timestamp":1604714570000},"page":"91-103","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata"],"prefix":"10.1007","author":[{"given":"Casey","family":"Keeler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,6]]},"reference":[{"issue":"1","key":"8_CR1","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"},{"key":"8_CR2","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_CR3","unstructured":"Holzer, M.: On emptiness and counting for alternating finite automata. In: Developments in Language Theory II, At the Crossroads of Mathematics, Computer Science and Biology, Magdeburg, Germany, 17\u201321 July 1995, pp. 88\u201397 (1995)"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-319-90530-3_16","volume-title":"Computer Science \u2013 Theory and Applications","author":"M Hospod\u00e1r","year":"2018","unstructured":"Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G., Kraj\u0148\u00e1kov\u00e1, I.: Operations on Boolean and alternating finite automata. In: Fomin, F.V., Podolskii, V.V. (eds.) CSR 2018. LNCS, vol. 10846, pp. 181\u2013193. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-90530-3_16"},{"issue":"2","key":"8_CR5","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. Inform. Comput 172(2), 202\u2013217 (2002)","journal-title":"Inform. Comput"},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/0022-0000(85)90063-7","volume":"31","author":"J Hromkovic","year":"1985","unstructured":"Hromkovic, J.: On the power of alternation in automata theory. J. Comput. Syst. Sci. 31(1), 28\u201339 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-030-40608-0_13","volume-title":"Language and Automata Theory and Applications","author":"C Keeler","year":"2020","unstructured":"Keeler, C., Salomaa, K.: Alternating finite automata with limited universal branching. In: Leporati, A., Mart\u00edn-Vide, C., Shapira, D., Zandron, C. (eds.) LATA 2020. LNCS, vol. 12038, pp. 196\u2013207. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-40608-0_13"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"King, K.N.: Alternating multihead finite automata (extended abstract). In: Automata, Languages and Programming, 8th Colloquium, Acre (Akko), Israel, July 13\u201317, 1981, Proceedings, pp. 506\u2013520 (1981)","DOI":"10.1007\/3-540-10843-2_40"},{"issue":"1","key":"8_CR9","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0304-3975(89)90023-6","volume":"67","author":"E Moriya","year":"1989","unstructured":"Moriya, E.: A grammatical characterization of alternating pushdown automata. Theor. Comput. Sci. 67(1), 75\u201385 (1989)","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20134","key":"8_CR10","first-page":"245","volume":"17","author":"A Palioudakis","year":"2012","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: State complexity of finite tree width NFAs. J. Autom. Lang. Comb. 17(2\u20134), 245\u2013264 (2012)","journal-title":"J. Autom. Lang. Comb."},{"issue":"6","key":"8_CR11","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B Ravikumar","year":"1989","unstructured":"Ravikumar, B., Ibarra, O.H.: Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput. 18(6), 1263\u20131282 (1989)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"8_CR12","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"WL Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. J. Comput. Syst. Sci. 21(2), 218\u2013235 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(91)90381-B","volume":"88","author":"A Weber","year":"1991","unstructured":"Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. Theoret. Comput. Sci. 88(2), 325\u2013349 (1991)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-62536-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T12:05:34Z","timestamp":1741608334000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-62536-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030625351","9783030625368"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-62536-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"6 November 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DCFS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Descriptional Complexity of Formal Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 August 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dcfs2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/sofl2020.conf.tuwien.ac.at\/DCFS2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}