{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,23]],"date-time":"2026-05-23T04:05:12Z","timestamp":1779509112767,"version":"3.53.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032026019","type":"print"},{"value":"9783032026026","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:00:00Z","timestamp":1755907200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:00:00Z","timestamp":1755907200000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-02602-6_5","type":"book-chapter","created":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T08:33:49Z","timestamp":1755851629000},"page":"55-72","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multi-entry DFA with\u00a0Reduced Initial States to\u00a0Speedup Parallel Recognition"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6444-0361","authenticated-orcid":false,"given":"Angelo","family":"Borsotti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5294-6840","authenticated-orcid":false,"given":"Luca","family":"Breveglieri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5061-7402","authenticated-orcid":false,"given":"Stefano","family":"Crespi Reghizzi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6469-2929","authenticated-orcid":false,"given":"Angelo","family":"Morzenti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,23]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2024.114621","volume":"1004","author":"C Bianchini","year":"2024","unstructured":"Bianchini, C., Policriti, A., Riccardi, B., Romanello, R.: Incremental NFA minimization. Theor. Comput. Sci. 1004, 114621 (2024). https:\/\/doi.org\/10.1016\/J.TCS.2024.114621","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"5_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/S00236-019-00363-5","volume":"58","author":"J Bj\u00f6rklund","year":"2021","unstructured":"Bj\u00f6rklund, J., Cleophas, L.: Aggregation-based minimization of finite-state automata. Acta Informatica 58(3), 177\u2013194 (2021). https:\/\/doi.org\/10.1007\/S00236-019-00363-5","journal-title":"Acta Informatica"},{"key":"5_CR3","doi-asserted-by":"publisher","unstructured":"Borsotti, A., Breveglieri, L., Crespi Reghizzi, S., Morzenti, A.: Minimizing speculation overhead in a parallel recognizer for regular texts. CoRR abs\/2412.14975 (2024). https:\/\/doi.org\/10.48550\/arXiv.2412.14975","DOI":"10.48550\/arXiv.2412.14975"},{"key":"5_CR4","doi-asserted-by":"publisher","unstructured":"Borsotti, A., Breveglieri, L., Crespi Reghizzi, S., Morzenti, A.: Minimizing speculation overhead in a parallel recognizer for regular texts. In: 30th Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2025, Las Vegas, NV, USA, 1\u20135 March 2025, pp. 569\u2013572. ACM (2025). https:\/\/doi.org\/10.1145\/3710848.3710866","DOI":"10.1145\/3710848.3710866"},{"key":"5_CR5","doi-asserted-by":"publisher","unstructured":"Brzozowski, J.A., Tamm, H.: Minimal nondeterministic finite automata and atoms of regular languages. CoRR abs\/1301.5585 (2013). https:\/\/doi.org\/10.48550\/arXiv.1301.5585","DOI":"10.48550\/arXiv.1301.5585"},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Fu, Z., Liu, Z., Li, J.: Efficient parallelization of regular expression matching for deep inspection. In: 26th International Conference on Computer Communication and Networks, ICCCN 2017, Vancouver, BC, Canada, 31 July\u20133 August 2017, pp.\u00a01\u20139. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/ICCCN.2017.8038377","DOI":"10.1109\/ICCCN.2017.8038377"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Galil, Z., Simon, J.: A note on multiple-entry finite automata. J. Comput. Syst. Sci. 12(3), 350\u2013351 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80006-2","DOI":"10.1016\/S0022-0000(76)80006-2"},{"issue":"41","key":"5_CR8","doi-asserted-by":"publisher","first-page":"5802","DOI":"10.1016\/J.TCS.2011.05.058","volume":"412","author":"P Garc\u00eda","year":"2011","unstructured":"Garc\u00eda, P., L\u00f3pez, D., Ruiz, J., Alvarez, G.I.: From regular expressions to smaller NFAs. Theor. Comput. Sci. 412(41), 5802\u20135807 (2011). https:\/\/doi.org\/10.1016\/J.TCS.2011.05.058","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"5_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-0000(74)80034-6","volume":"9","author":"A Gill","year":"1974","unstructured":"Gill, A., Kou, L.T.: Multiple-entry finite automata. J. Comput. Syst. Sci. 9(1), 1\u201319 (1974). https:\/\/doi.org\/10.1016\/S0022-0000(74)80034-6","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"5_CR10","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/J.JCSS.2006.11.002","volume":"73","author":"G Gramlich","year":"2007","unstructured":"Gramlich, G., Schnitger, G.: Minimizing NFAs and regular expressions. J. Comput. Syst. Sci. 73(6), 908\u2013923 (2007). https:\/\/doi.org\/10.1016\/J.JCSS.2006.11.002","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR11","doi-asserted-by":"publisher","unstructured":"Hillis, W.D., Steele, Jr., G.L.: Data parallel algorithms. Commun. ACM 29(12), 1170\u20131183 (1986). https:\/\/doi.org\/10.1145\/7902.7903","DOI":"10.1145\/7902.7903"},{"key":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-642-02979-0_9","volume-title":"Implementation and Application of Automata","author":"J Holub","year":"2009","unstructured":"Holub, J., \u0160tekr, S.: On parallel implementations of deterministic finite automata. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol. 5642, pp. 54\u201364. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02979-0_9"},{"key":"5_CR13","doi-asserted-by":"publisher","unstructured":"Holzer, M., Salomaa, K., Yu, S.: On the state complexity of $$k$$-entry deterministic finite automata. J. Autom. Lang. Comb. 6(4), 453\u2013466 (2001). https:\/\/doi.org\/10.25596\/JALC-2001-453","DOI":"10.25596\/JALC-2001-453"},{"key":"5_CR14","doi-asserted-by":"publisher","unstructured":"Kappes, M.: Descriptional complexity of deterministic finite automata with multiple initial states. J. Autom. Lang. Comb. 5(3), 269\u2013278 (2000). https:\/\/doi.org\/10.25596\/JALC-2000-269","DOI":"10.25596\/JALC-2000-269"},{"issue":"3","key":"5_CR15","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/s10766-013-0258-5","volume":"42","author":"Y Ko","year":"2013","unstructured":"Ko, Y., Jung, M., Han, Y.-S., Burgstaller, B.: A speculative parallel DFA membership test for multicore, SIMD and cloud computing environments. Int. J. Parallel Prog. 42(3), 456\u2013489 (2013). https:\/\/doi.org\/10.1007\/s10766-013-0258-5","journal-title":"Int. J. Parallel Prog."},{"issue":"4","key":"5_CR16","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"RE Ladner","year":"1980","unstructured":"Ladner, R.E., Fischer, M.J.: Parallel prefix computation. J. ACM 27(4), 831\u2013838 (1980). https:\/\/doi.org\/10.1145\/322217.322232","journal-title":"J. ACM"},{"issue":"1\u20134","key":"5_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.3233\/FI-222126","volume":"186","author":"S Lombardy","year":"2022","unstructured":"Lombardy, S., Sakarovitch, J.: Morphisms and minimisation of weighted automata. Fundam. Informaticae 186(1\u20134), 195\u2013218 (2022). https:\/\/doi.org\/10.3233\/FI-222126","journal-title":"Fundam. Informaticae"},{"key":"5_CR18","doi-asserted-by":"publisher","unstructured":"McNaughton, R., Yamada, H.: Regular expressions and state graphs for automata. IRE Trans. Electron. Comput. EC-9(1), 39\u201347 (1960). https:\/\/doi.org\/10.1109\/TEC.1960.5221603","DOI":"10.1109\/TEC.1960.5221603"},{"key":"5_CR19","doi-asserted-by":"publisher","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: 13th Annual Symposium on Switching and Automata Theory, SWAT 1972, College Park, MD, USA, 25\u201327 October 1972, pp. 125\u2013129. IEEE Computer Society (1972). https:\/\/doi.org\/10.1109\/SWAT.1972.29","DOI":"10.1109\/SWAT.1972.29"},{"key":"5_CR20","doi-asserted-by":"publisher","unstructured":"Mytkowicz, T., Musuvathi, M., Schulte, W.: Data-parallel finite-state machines. In: Balasubramonian, R., Davis, A., Adve, S.V. (eds.) Architectural Support for Programming Languages and Operating Systems \u2013 19th International Conference, ASPLOS 2014, Salt Lake City, UT, USA, 1\u20135 March 2014, pp. 529\u2013542. ACM (2014). https:\/\/doi.org\/10.1145\/2541940.2541988","DOI":"10.1145\/2541940.2541988"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-642-39310-5_22","volume-title":"Descriptional Complexity of Formal Systems","author":"A Palioudakis","year":"2013","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: Finite nondeterminism vs. DFAs with multiple initial states. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 229\u2013240. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39310-5_22"},{"key":"5_CR22","doi-asserted-by":"publisher","unstructured":"Qiu, J., Sun, X., Sabet, A.H.N., Zhao, Z.: Scalable FSM parallelization via path fusion and higher-order speculation. In: Sherwood, T., Berger, E.D., Kozyrakis, C. (eds.) Architectural Support for Programming Languages and Operating Systems \u2013 26th International Conference, ASPLOS 2021, Virtual Event, USA, 19\u201323 April 2021, pp. 887\u2013901. ACM (2021). https:\/\/doi.org\/10.1145\/3445814.3446705","DOI":"10.1145\/3445814.3446705"},{"key":"5_CR23","doi-asserted-by":"publisher","unstructured":"Sin\u2019ya, R., Matsuzaki, K., Sassa, M.: Simultaneous finite automata: an efficient data-parallel model for regular expression matching. In: 42nd International Conference on Parallel Processing, ICPP 2013, Lyon, France, 1\u20134 October 2013, pp. 220\u2013229. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/ICPP.2013.31","DOI":"10.1109\/ICPP.2013.31"},{"issue":"3","key":"5_CR24","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/0022-0000(79)90038-2","volume":"18","author":"PAS Veloso","year":"1979","unstructured":"Veloso, P.A.S., Gill, A.: Some remarks on multiple-entry finite automata. J. Comput. Syst. Sci. 18(3), 304\u2013306 (1979). https:\/\/doi.org\/10.1016\/0022-0000(79)90038-2","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR25","doi-asserted-by":"publisher","unstructured":"Yang, Y.E., Prasanna, V.K.: Space-time tradeoff in regular expression matching with semi-deterministic finite automata. In: 30th International Conference on Computer Communications \u2013 Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2011, Shanghai, China, 10\u201315 April 2011, pp. 1853\u20131861. IEEE Computer Society (2011). https:\/\/doi.org\/10.1109\/INFCOM.2011.5934986","DOI":"10.1109\/INFCOM.2011.5934986"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-02602-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,23]],"date-time":"2026-05-23T03:23:24Z","timestamp":1779506604000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-02602-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,23]]},"ISBN":["9783032026019","9783032026026"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-02602-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,23]]},"assertion":[{"value":"23 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Palermo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","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 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ciaa2025.unipa.it","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}