{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:14:29Z","timestamp":1742912069000,"version":"3.40.3"},"publisher-location":"Cham","reference-count":11,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031721991"},{"type":"electronic","value":"9783031722004"}],"license":[{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"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-72200-4_3","type":"book-chapter","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:50Z","timestamp":1726686110000},"page":"26-40","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Indexing Finite-State Automata Using Forward-Stable Partitions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3495-3753","authenticated-orcid":false,"given":"Ruben","family":"Becker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1117-5020","authenticated-orcid":false,"given":"Sung-Hwan","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3553-4953","authenticated-orcid":false,"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5149-2416","authenticated-orcid":false,"given":"Carlo","family":"Tosoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Alanko, J., D\u2019Agostino, G., Policriti, A., Prezza, N.: Regular languages meet prefix sorting. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5\u20138 January 2020, pp. 911\u2013930. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.55","DOI":"10.1137\/1.9781611975994.55"},{"key":"3_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/J.IC.2021.104820","volume":"281","author":"J Alanko","year":"2021","unstructured":"Alanko, J., D\u2019Agostino, G., Policriti, A., Prezza, N.: Wheeler languages. Inf. Comput. 281, 104820 (2021). https:\/\/doi.org\/10.1016\/J.IC.2021.104820","journal-title":"Inf. Comput."},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Becker, R., et al.: Sorting finite automata via partition refinement. In: G\u00f8rtz, I.L., Farach-Colton, M., Puglisi, S.J., Herman, G. (eds.) 31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, The Netherlands, 4\u20136 September 2023. LIPIcs, vol.\u00a0274, pp. 15:1\u201315:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2023.15","DOI":"10.4230\/LIPICS.ESA.2023.15"},{"key":"3_CR4","unstructured":"Becker, R., Kim, S.H., Prezza, N., Tosoni, C.: Indexing finite-state automata using forward-stable partitions (2024). https:\/\/arxiv.org\/abs\/2406.02763"},{"key":"3_CR5","unstructured":"Burrows, M., Wheeler, D.: A block-sorting lossless data compression algorithm. SRS Res. Rep. 124 (1994)"},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"Cotumaccio, N.: Graphs can be succinctly indexed for pattern matching in $$O(\\vert E\\vert ^{2}+\\vert V\\vert ^{5\/2})$$ time. In: Bilgin, A., Marcellin, M.W., Serra-Sagrist\u00e0, J., Storer, J.A. (eds.) Data Compression Conference, DCC 2022, Snowbird, UT, USA 22\u201325, March 2022, pp. 272\u2013281. IEEE (2022). https:\/\/doi.org\/10.1109\/DCC52660.2022.00035","DOI":"10.1109\/DCC52660.2022.00035"},{"key":"3_CR7","doi-asserted-by":"publisher","unstructured":"Cotumaccio, N., Prezza, N.: On indexing and compressing finite automata. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10\u201313 January 2021, pp. 2585\u20132599. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.153","DOI":"10.1137\/1.9781611976465.153"},{"key":"3_CR8","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, 12\u201314 November 2000, pp. 390\u2013398. IEEE Computer Society (2000). https:\/\/doi.org\/10.1109\/SFCS.2000.892127","DOI":"10.1109\/SFCS.2000.892127"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/J.TCS.2017.06.016","volume":"698","author":"T Gagie","year":"2017","unstructured":"Gagie, T., Manzini, G., Sir\u00e9n, J.: Wheeler graphs: a framework for BWT-based data structures. Theor. Comput. Sci. 698, 67\u201378 (2017). https:\/\/doi.org\/10.1016\/J.TCS.2017.06.016","journal-title":"Theor. Comput. Sci."},{"key":"3_CR10","doi-asserted-by":"publisher","unstructured":"Gibney, D., Thankachan, S.V.: On the hardness and inapproximability of recognizing wheeler graphs. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, Munich\/Garching, Germany, 9\u201311 September 2019. LIPIcs, vol.\u00a0144, pp. 51:1\u201351:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2019.51","DOI":"10.4230\/LIPICS.ESA.2019.51"},{"issue":"6","key":"3_CR11","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973\u2013989 (1987). https:\/\/doi.org\/10.1137\/0216062","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-72200-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:02:08Z","timestamp":1726686128000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72200-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"ISBN":["9783031721991","9783031722004"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72200-4_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,9,19]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Vallarta","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/computo.fismat.umich.mx\/spire2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}