{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:01:12Z","timestamp":1780743672218,"version":"3.54.1"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032014740","type":"print"},{"value":"9783032014757","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,8,17]],"date-time":"2025-08-17T00:00:00Z","timestamp":1755388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,17]],"date-time":"2025-08-17T00:00:00Z","timestamp":1755388800000},"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-01475-7_4","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T17:39:20Z","timestamp":1755365960000},"page":"45-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Universally Wheeler Languages"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3495-3753","authenticated-orcid":false,"given":"Ruben","family":"Becker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1838-9785","authenticated-orcid":false,"given":"Giuseppa","family":"Castiglione","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8920-483X","authenticated-orcid":false,"given":"Giovanna","family":"D\u2019Agostino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8502-5896","authenticated-orcid":false,"given":"Alberto","family":"Policriti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3553-4953","authenticated-orcid":false,"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1972-6931","authenticated-orcid":false,"given":"Antonio","family":"Restivo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4925-9529","authenticated-orcid":false,"given":"Brian","family":"Riccardi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"104820","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":"4_CR2","doi-asserted-by":"crossref","unstructured":"Becker, R., et al.: Universally wheeler languages. arXiv:2504.19537 (2025)","DOI":"10.1007\/978-3-032-01475-7_4"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Becker, R., Cenzato, D., Kim, S.H., Kodric, B., Policriti, A., Prezza, N.: Optimal wheeler language recognition. In: International Symposium on String Processing and Information Retrieval, pp. 62\u201374. Springer (2023)","DOI":"10.1007\/978-3-031-43980-3_6"},{"issue":"3","key":"4_CR4","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0012-365X(73)80005-6","volume":"4","author":"J Brzozowski","year":"1973","unstructured":"Brzozowski, J.: Characterizations of locally testable events. Discrete Math. 4(3), 243\u2013271 (1973). https:\/\/doi.org\/10.1016\/S0012-365X(73)80005-6","journal-title":"Discrete Math."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"1175","DOI":"10.1007\/s00224-017-9803-8","volume":"62","author":"JA Brzozowski","year":"2018","unstructured":"Brzozowski, J.A., Szyku\u0142a, M., Ye, Y.: Syntactic complexity of regular ideals. Theory Comput. Syst. 62, 1175\u20131202 (2018)","journal-title":"Theory Comput. Syst."},{"key":"4_CR6","doi-asserted-by":"publisher","unstructured":"Caron, P.: Families of locally testable languages. Theor. Comput. Sci. 242(1-2), 361\u2013376 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(98)00332-6","DOI":"10.1016\/S0304-3975(98)00332-6"},{"key":"4_CR7","unstructured":"Castiglione, G., Restivo, A.: Completing wheeler automata. In: de\u2019Liguoro, U., Palazzo, M., Roversi, L. (eds.) Proceedings of the 25th Italian Conference on Theoretical Computer Science, Torino, Italy, September 11\u201313, 2024. CEUR Workshop Proceedings, vol.\u00a03811, pp. 120\u2013132. CEUR-WS.org (2024). https:\/\/ceur-ws.org\/Vol-3811\/paper060.pdf"},{"key":"4_CR8","doi-asserted-by":"publisher","unstructured":"Cotumaccio, N., D\u2019Agostino, G., Policriti, A., Prezza, N.: Co-lexicographically ordering automata and regular languages - part I. J. ACM 70(4), 27:1\u201327:73 (2023). https:\/\/doi.org\/10.1145\/3607471","DOI":"10.1145\/3607471"},{"key":"4_CR9","unstructured":"D\u2019Agostino, G., Martincigh, D., Policriti, A.: Ordering regular languages: a danger zone. In: Coen, C.S., Salvo, I. (eds.) Proceedings of the 22nd Italian Conference on Theoretical Computer Science, Bologna, Italy, September 13\u201315, 2021. CEUR Workshop Proceedings, vol.\u00a03072, pp. 46\u201369. CEUR-WS.org (2021). https:\/\/ceur-ws.org\/Vol-3072\/paper5.pdf"},{"key":"4_CR10","doi-asserted-by":"publisher","unstructured":"D\u2019Agostino, G., Martincigh, D., Policriti, A.: Ordering regular languages and automata: complexity. Theor. Comput. Sci. 949, 113709 (2023). https:\/\/doi.org\/10.1016\/J.TCS.2023.113709","DOI":"10.1016\/J.TCS.2023.113709"},{"key":"4_CR11","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005). https:\/\/doi.org\/10.1145\/1082036.1082039","DOI":"10.1145\/1082036.1082039"},{"key":"4_CR12","doi-asserted-by":"publisher","unstructured":"Gagie, T., Manzini, G., Sir\u00e9n, J.: Wheeler graphs: a framework for BWT-based data structures. Theor. Comput. Sci. 698, 67 \u2013 78 (2017). Algorithms, Strings and Theoretical Approaches in the Big Data Era (In Honor of the 60th Birthday of Professor Raffaele Giancarlo). https:\/\/doi.org\/10.1016\/j.tcs.2017.06.016","DOI":"10.1016\/j.tcs.2017.06.016"},{"key":"4_CR13","doi-asserted-by":"publisher","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM 67(1), 2:1\u20132:54 (2020). https:\/\/doi.org\/10.1145\/3375890","DOI":"10.1145\/3375890"},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/568438.568455","volume":"32","author":"JE Hopcroft","year":"2001","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, languages, and computation. ACM SIGACT News 32(1), 60\u201365 (2001)","journal-title":"ACM SIGACT News"},{"issue":"2","key":"4_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR16","unstructured":"Vassilevska\u00a0Williams, V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), pp. 17\u201329. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2015)"},{"issue":"2\u20133","key":"4_CR17","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.023","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01475-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T15:11:58Z","timestamp":1757430718000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01475-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,17]]},"ISBN":["9783032014740","9783032014757"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01475-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,17]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","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":"19 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 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":"dlt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cida.uos.ac.kr\/dlt2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}