{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T17:50:04Z","timestamp":1777053004347,"version":"3.51.4"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031970993","type":"print"},{"value":"9783031971006","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-97100-6_2","type":"book-chapter","created":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T10:08:44Z","timestamp":1751278124000},"page":"17-33","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Close Analysis of\u00a0the\u00a0Subset Construction"],"prefix":"10.1007","author":[{"given":"Ivan","family":"Baburin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Cotterell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,29]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Allauzen, C., Riley, M., Schalkwyk, J., Skut, W., Mohri, M.: OpenFST: a general and efficient weighted finite-state transducer library: (extended abstract of an invited talk). In: Implementation and Application of Automata: 12th International Conference, pp. 11\u201323 (2007)","DOI":"10.1007\/978-3-540-76336-9_3"},{"key":"2_CR2","unstructured":"Baburin, I., Cotterell, R.: An analysis of on-the-fly determinization of finite-state automata (2023)"},{"issue":"2","key":"2_CR3","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/2713167","volume":"58","author":"F Bonchi","year":"2015","unstructured":"Bonchi, F., Pous, D.: Hacking nondeterminism with induction and coinduction. Commun. ACM 58(2), 87\u201395 (2015)","journal-title":"Commun. ACM"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Bordihn, H., Holzer, M., Kutrib, M.: Determination of finite automata accepting subregular languages. Theor. Comput. Sci. 410(35), 3209\u20133222 (2009). descriptional Complexity of Formal Systems","DOI":"10.1016\/j.tcs.2009.05.019"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2014.04.016","volume":"539","author":"J Brzozowski","year":"2014","unstructured":"Brzozowski, J., Tamm, H.: Theory of \u00e1tomata. Theoret. Comput. Sci. 539, 13\u201327 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR6","unstructured":"Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Proceedings of the Symposium on Mathematical Theory of Automata, pp. 529\u2013561 (1962)"},{"issue":"39","key":"2_CR7","doi-asserted-by":"publisher","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"BM Bui-Xuan","year":"2011","unstructured":"Bui-Xuan, B.M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theoret. Comput. Sci. 412(39), 5187\u20135204 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"2_CR8","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(00)00293-0","volume":"267","author":"JM Champarnaud","year":"2001","unstructured":"Champarnaud, J.M.: Subset construction complexity for homogeneous automata, position automata and ZPC-structures. Theoret. Comput. Sci. 267(1\u20132), 17\u201334 (2001)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(92)90002-W","volume":"97","author":"S Cho","year":"1992","unstructured":"Cho, S., Huynh, D.T.: The parallel complexity of finite-state automata problems. Inf. Comput. 97(1), 1\u201322 (1992)","journal-title":"Inf. Comput."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"De\u00a0Wulf, M., Doyen, L., Henzinger, T.A., Raskin, J.F.: Antichains: a new algorithm for checking universality of finite automata. In: Computer Aided Verification, pp. 17\u201330 (2006)","DOI":"10.1007\/11817963_5"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Meyer, A.R.: Economy of description by automata, grammars, and formal systems. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 188\u2013191. IEEE Computer Society (1971)","DOI":"10.1109\/SWAT.1971.11"},{"issue":"3","key":"2_CR12","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata\u2013a survey. Inf. Comput. 209(3), 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Association for Computing Machinery (2001)","DOI":"10.1145\/568438.568455"},{"key":"2_CR14","unstructured":"(https:\/\/cstheory.stackexchange.com\/users\/64968\/stefan kiefer), S.K.: Complexity of NFA to DFA minimization with binary threshold. Theoretical Computer Science Stack Exchange. https:\/\/cstheory.stackexchange.com\/q\/50706"},{"issue":"1","key":"2_CR15","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF01375471","volume":"11","author":"DE Knuth","year":"1991","unstructured":"Knuth, D.E.: Efficient representation of perm groups. Combinatorica 11(1), 33\u201343 (1991)","journal-title":"Combinatorica"},{"issue":"05","key":"2_CR16","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1142\/S0129054105003418","volume":"16","author":"H Leung","year":"2005","unstructured":"Leung, H.: Descriptional complexity of NFA of different ambiguity. Int. J. Found. Comput. Sci. 16(05), 975\u2013984 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"10","key":"2_CR17","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"100","author":"FR Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. 100(10), 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Pin, J.E.: Syntactic semigroups. Handbook of Formal Languages: Volume 1 Word, Language, Grammar, pp. 679\u2013746 (1997)","DOI":"10.1007\/978-3-642-59136-5_10"},{"issue":"4","key":"2_CR19","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"JS Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12(4), 777\u2013788 (1983)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2_CR20","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"issue":"2","key":"2_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR22","unstructured":"Vatshelle, M.: New Width Parameters of Graphs. Ph.D. Thesis, University of Bergen (2012)"}],"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-031-97100-6_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T17:30:57Z","timestamp":1777051857000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-97100-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031970993","9783031971006"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-97100-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"29 June 2025","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":"Loughborough","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dcfs2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.lboro.ac.uk\/departments\/compsci\/events\/dcfs-2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}