{"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":1771745362605,"version":"3.50.1"},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030934880","type":"print"},{"value":"9783030934897","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-93489-7_8","type":"book-chapter","created":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:30:01Z","timestamp":1640997001000},"page":"88-99","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Width Measures of\u00a0Alternating 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":[[2022,1,1]]},"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."},{"issue":"2","key":"8_CR3","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"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2020.12.011","volume":"870","author":"CA Kapoutsis","year":"2021","unstructured":"Kapoutsis, C.A., Zakzok, M.: Alternation in two-way finite automata. Theor. Comput. Sci. 870, 75\u2013102 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-030-23247-4_16","volume-title":"Descriptional Complexity of Formal Systems","author":"C Keeler","year":"2019","unstructured":"Keeler, C., Salomaa, K.: Nondeterminism growth and state complexity. In: Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G., Konstantinidis, S. (eds.) DCFS 2019. LNCS, vol. 11612, pp. 210\u2013222. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-23247-4_16"},{"key":"8_CR6","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_CR7","doi-asserted-by":"publisher","unstructured":"Keeler, C., Salomaa, K.: Combining limited parallelism and nondeterminism in alternating finite automata. In: Jir\u00e1skov\u00e1, G., Pighizzini, G. (eds.) DCFS 2020. LNCS, vol. 12442, pp. 91\u2013103. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-62536-8_8","DOI":"10.1007\/978-3-030-62536-8_8"},{"issue":"1","key":"8_CR8","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"RE Ladner","year":"1984","unstructured":"Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM J. Comput. 13(1), 135\u2013155 (1984)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"8_CR9","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/S0097539793252092","volume":"27","author":"H Leung","year":"1998","unstructured":"Leung, H.: Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM J. Comput 27(4), 1073\u20131082 (1998)","journal-title":"SIAM J. Comput"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: SWAT (FOCS) 1971, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"issue":"2\u20134","key":"8_CR11","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. Combin. 17(2\u20134), 245\u2013264 (2012)","journal-title":"J. Autom. Lang. Combin."},{"issue":"2","key":"8_CR12","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. Theor. Comput. Sci. 88(2), 325\u2013349 (1991)","journal-title":"Theor. 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-93489-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T01:04:19Z","timestamp":1767229459000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-93489-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030934880","9783030934897"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-93489-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"1 January 2022","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":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dcfs2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/toc.yonsei.ac.kr\/dcfs2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}