{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:07:28Z","timestamp":1771700848187,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T00:00:00Z","timestamp":1749513600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T00:00:00Z","timestamp":1749513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["OGP0147224"],"award-info":[{"award-number":["OGP0147224"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["OGP0147224"],"award-info":[{"award-number":["OGP0147224"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s11047-025-10022-z","type":"journal-article","created":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T04:49:43Z","timestamp":1749530983000},"page":"541-556","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms for maximal existential and universal width"],"prefix":"10.1007","volume":"24","author":[{"given":"John","family":"Alajaji","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":[[2025,6,10]]},"reference":[{"issue":"1","key":"10022_CR2","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"AK Chandra","year":"1981","unstructured":"Chandra AK, Kozen DC, Stockmeyer LJ (1981) Alternation. J ACM 28(1):114\u2013133. https:\/\/doi.org\/10.1145\/322234.322243","journal-title":"J ACM"},{"issue":"2","key":"10022_CR3","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M Chrobak","year":"1986","unstructured":"Chrobak M (1986) Finite automata and unary languages. Theor Comput Sci 47(2):149\u2013158. https:\/\/doi.org\/10.1016\/0304-3975(86)90142-8","journal-title":"Theor Comput Sci"},{"key":"10022_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-19-0957-3","volume-title":"A first course in graph theory and combinatorics","author":"S Cioaba","year":"2022","unstructured":"Cioaba S, Murty R (2022) A first course in graph theory and combinatorics, 2nd edn. Springer, Singapore. https:\/\/doi.org\/10.1007\/978-981-19-0957-3","edition":"2"},{"key":"10022_CR5","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL et al (2009) Introduction to algorithms, 3rd edn. The MIT Press, Cambridge","edition":"3"},{"issue":"2","key":"10022_CR6","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0890-5401(90)90053-K","volume":"86","author":"J Goldstine","year":"1990","unstructured":"Goldstine J, Kintala CMR, Wotschke D (1990) On measuring nondeterminism in regular languages. Inf Comput 86(2):179\u2013194. https:\/\/doi.org\/10.1016\/0890-5401(90)90053-K","journal-title":"Inf Comput"},{"key":"10022_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 et al (2002) Communication complexity method for measuring nondeterminism in finite automata. Inf Comput 172:202\u2013217. https:\/\/doi.org\/10.1006\/inco.2001.3069","journal-title":"Inf Comput"},{"issue":"1","key":"10022_CR1","volume":"1045","author":"A John","year":"2024","unstructured":"John A, Kai S (2024) Maximal universal width of an AFA is NP-hard. Theor Comput Sci 1045(1):115280","journal-title":"Theor Comput Sci"},{"key":"10022_CR9","unstructured":"Keeler C (2021) Finite automata with restricted nondeterminism and universality. PhD thesis, Queen\u2019s University"},{"key":"10022_CR10","doi-asserted-by":"publisher","unstructured":"Keeler C, Salomaa K (2020) Combining limited parallelism and nondeterminism in alternating finite automata. In: International conference descriptional complexity of formal systems, DCFS, Lecture Notes in Computer Science, vol 12442. Springer, Cham, pp 91\u2013103, https:\/\/doi.org\/10.1007\/978-3-030-62536-8_8","DOI":"10.1007\/978-3-030-62536-8_8"},{"key":"10022_CR11","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-030-93489-7_8","volume-title":"Descriptional complexity of formal systems","author":"C Keeler","year":"2021","unstructured":"Keeler C, Kai S (2021) Width measures of alternating finite automata. In: Han Y-S, Ko S-K (eds) Descriptional complexity of formal systems. Springer, Cham, pp 88\u201399. https:\/\/doi.org\/10.1007\/978-3-030-93489-7_8"},{"issue":"1","key":"10022_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.7561\/SACS.2023.1.53","volume":"33","author":"C Keeler","year":"2023","unstructured":"Keeler C, Salomaa K (2023) Maximal existential and universal width. Sci Ann Comput Sci 33(1):53\u201377. https:\/\/doi.org\/10.7561\/SACS.2023.1.53","journal-title":"Sci Ann Comput Sci"},{"key":"10022_CR13","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF00263994","volume":"13","author":"CMR Kintala","year":"1980","unstructured":"Kintala CMR, Wotschke D (1980) Amounts of nondeterminism in finite automata. Acta Inf 13:199\u2013204. https:\/\/doi.org\/10.1007\/BF00263994","journal-title":"Acta Inf"},{"issue":"7","key":"10022_CR14","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s002360050133","volume":"35","author":"H Leung","year":"1998","unstructured":"Leung H (1998) On finite automata with limited nondeterminism. Acta Inf 35(7):595\u2013624. https:\/\/doi.org\/10.1007\/s002360050133","journal-title":"Acta Inf"},{"issue":"2\u20134","key":"10022_CR15","doi-asserted-by":"publisher","first-page":"245","DOI":"10.5555\/3173440.3173451","volume":"17","author":"A Palioudakis","year":"2012","unstructured":"Palioudakis A, Salomaa K, Akl SG (2012) State complexity of finite tree width NFAs. J Automata Lang Comb 17(2\u20134):245\u2013274. https:\/\/doi.org\/10.5555\/3173440.3173451","journal-title":"J Automata Lang Comb"},{"key":"10022_CR16","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-319-62809-7_23","volume-title":"Developments in language theory","author":"G Pighizzini","year":"2017","unstructured":"Pighizzini G, Prigioniero L (2017) Limited automata and unary languages. In: Charlier \u00c9, Leroy J, Rigo M (eds) Developments in language theory. Springer, Cham, pp 308\u2013319. https:\/\/doi.org\/10.1007\/978-3-319-62809-7_23"},{"issue":"6","key":"10022_CR17","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B Ravikumar","year":"1989","unstructured":"Ravikumar B, Ibarra OH (1989) Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J Comput 18(6):1263\u20131282. https:\/\/doi.org\/10.1137\/0218083","journal-title":"SIAM J Comput"},{"key":"10022_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511808876","volume-title":"A second course in formal languages and automata theory","author":"J Shallit","year":"2008","unstructured":"Shallit J (2008) A second course in formal languages and automata theory. Cambridge University Press, Cambridge. https:\/\/doi.org\/10.1017\/CBO9780511808876"},{"key":"10022_CR19","volume-title":"Introduction to the theory of computation","author":"M Sipser","year":"2013","unstructured":"Sipser M (2013) Introduction to the theory of computation, 3rd edn. Cengage Learning, Boston","edition":"3"},{"key":"10022_CR20","doi-asserted-by":"publisher","unstructured":"Tarjan R (1971) Depth-first search and linear graph algorithms. In: 12th annual symposium on switching and automata theory (swat 1971), pp 114\u2013121. https:\/\/doi.org\/10.1109\/SWAT.1971.10","DOI":"10.1109\/SWAT.1971.10"},{"key":"10022_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-031-34326-1_4","volume-title":"Descriptional complexity of formal systems","author":"H Yo-Sub","year":"2023","unstructured":"Yo-Sub H, Sungmin K, Sang-Ki K et al (2023) Existential and universal width of alternating finite automata. In: Bordihn H, Tran N, Vaszil G (eds) Descriptional complexity of formal systems. Springer, Cham, pp 51\u201364. https:\/\/doi.org\/10.1007\/978-3-031-34326-1_4"},{"key":"10022_CR21","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-59126-6","volume-title":"Handbook of formal languages","author":"S Yu","year":"1997","unstructured":"Yu S (1997) Beyond words. In: Rozenberg G, Salomaa A (eds) Handbook of formal languages, vol 1. Springer, Berlin, pp 41\u2013110. https:\/\/doi.org\/10.1007\/978-3-642-59126-6"},{"key":"10022_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114506","author":"M Zakzok","year":"2024","unstructured":"Zakzok M, Salomaa K (2024) Converting finite width AFAs to nondeterministic and universal finite automata. Theor Comput Sci. https:\/\/doi.org\/10.1016\/j.tcs.2024.114506","journal-title":"Theor Comput Sci"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10022-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-025-10022-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10022-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:48:27Z","timestamp":1771699707000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-025-10022-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10022"],"URL":"https:\/\/doi.org\/10.1007\/s11047-025-10022-z","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"5 May 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2026","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised to correct overlapping text in the computation trees section.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}