{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T20:04:32Z","timestamp":1785182672002,"version":"3.55.0"},"publisher-location":"Cham","reference-count":50,"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_18","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T17:39:26Z","timestamp":1755365966000},"page":"261-277","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Jumbled Scattered Factors"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1531-7970","authenticated-orcid":false,"given":"Pamela","family":"Fleischmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1145-5806","authenticated-orcid":false,"given":"Annika","family":"Huch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Melf","family":"Kammholz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6002-1581","authenticated-orcid":false,"given":"Tore","family":"Ko\u00df","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"18_CR1","unstructured":"Adamson, D., Fleischmann, P., Huch, A., Ko\u00df, T., Manea, F., Nowotka, D.: k-universality of regular languages. In: ISAAC 2023. LIPIcs, vol. 283, pp. 4:1\u20134:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Adamson, D., Fleischmann, P., Huch, A., Wiedenh\u00f6ft, M.: Tight bounds for the number of absent scattered factors. arXiv preprint arXiv:2407.18599 (2024)","DOI":"10.1007\/978-3-032-04700-7_2"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Artikis, A., Margara, A., Ugarte, M., Vansummeren, S., Weidlich, M.: Complex event recognition languages: tutorial. In: DEBS, pp. 7\u201310 (2017)","DOI":"10.1145\/3093742.3095106"},{"issue":"2","key":"18_CR4","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"RA Baeza-Yates","year":"1991","unstructured":"Baeza-Yates, R.A.: Searching subsequences. Theor. Comput. Sci. 78(2), 363\u2013376 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Bannai, H., I, T., Kociumaka, T., K\u00f6ppl, D., Puglisi, S.J.: Computing longest Lyndon subsequences and longest common Lyndon subsequences. Algorithmica 86(3), 735\u2013756 (2024)","DOI":"10.1007\/s00453-023-01125-z"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-030-48516-0_2","volume-title":"Developments in Language Theory","author":"L Barker","year":"2020","unstructured":"Barker, L., Fleischmann, P., Harwardt, K., Manea, F., Nowotka, D.: Scattered factor-universality of words. In: Jonoska, N., Savchuk, D. (eds.) DLT 2020. LNCS, vol. 12086, pp. 14\u201328. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-48516-0_2"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Baumann, P., Ganardi, M., Thinniyam, R.S., Zetzsche, G.: Existential definability over the subword ordering. Log. Methods Comput. Sci. 19(4) (2023)","DOI":"10.46298\/lmcs-19(4:35)2023"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Multivariate fine-grained complexity of longest common subsequence. In: SODA 2018, pp. 1216\u20131235. SIAM (2018)","DOI":"10.1137\/1.9781611975031.79"},{"issue":"2","key":"18_CR9","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1142\/S0129054112400175","volume":"23","author":"P Burcsi","year":"2012","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Lipt\u00e1k, Z.: Algorithms for jumbled pattern matching in strings. Int. J. Found. Comput. Sci. 23(2), 357\u2013374 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"18_CR10","unstructured":"Day, J.D., Fleischmann, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: The edit distance to k-subsequence universality. In: STACS 2021. LIPIcs, vol. 187, pp. 25:1\u201325:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Do, D.T., Le, T.T.Q., Le, N.-Q.-K.: Using deep neural networks and biological subwords to detect protein s-sulfenylation sites. Brief. Bioinform. 22(3) (2021)","DOI":"10.1093\/bib\/bbaa128"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s00026-004-0232-4","volume":"8","author":"AWM Dress","year":"2005","unstructured":"Dress, A.W.M., Erd\u0151s, P.L.: Reconstructing words from subwords in linear time. Ann. Comb. 8, 457\u2013462 (2005)","journal-title":"Ann. Comb."},{"key":"18_CR13","unstructured":"Fazekas, S.Z., Ko\u00df, T., Manea, F., Mercas, R., Specht, T.: Subsequence matching and analysis problems for formal languages. In: ISAAC 2024. LIPIcs, vol. 322, pp. 28:1\u201328:23 (2024)"},{"key":"18_CR14","unstructured":"Fleischmann, P., Germann, S.B., Nowotka, D.: Scattered factor universality\u2013the power of the remainder. arXiv preprint arXiv:2104.09063 (published at RuFiDim) (2021)"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"114113","DOI":"10.1016\/j.tcs.2023.114113","volume":"974","author":"P Fleischmann","year":"2023","unstructured":"Fleischmann, P., Haschke, L., H\u00f6fer, J., Huch, A., Mayrock, A., Nowotka, D.: Nearly k-universal words - investigating a part of Simon\u2019s congruence. Theor. Comput. Sci. 974, 114113 (2023)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., H\u00f6fer, J., Huch, A., Nowotka, D.: $$\\alpha $$-$$\\beta $$-factorization and the binary case of Simon\u2019s congruence. In: FCT 2023. LNCS, vol. 14292, pp. 190\u2013204. Springer (2023)","DOI":"10.1007\/978-3-031-43587-4_14"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Fleischmann, P., Kim, S., Ko\u00df, T., Manea, F., Nowotka, D., Siemer, S., Wiedenh\u00f6ft, M.: Matching patterns with variables under Simon\u2019s congruence. In: RP 2023. LNCS, vol. 14235, pp. 155\u2013170. Springer (2023)","DOI":"10.1007\/978-3-031-45286-4_12"},{"issue":"6","key":"18_CR18","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1142\/S0129054121420016","volume":"32","author":"P Fleischmann","year":"2021","unstructured":"Fleischmann, P., Lejeune, M., Manea, F., Nowotka, D., Rigo, M.: Reconstructing words from right-bounded-block words. Int. J. Found. Comput. Sci. 32(6), 619\u2013640 (2021)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"102482","DOI":"10.1016\/j.aam.2022.102482","volume":"145","author":"PJ Forrester","year":"2023","unstructured":"Forrester, P.J., Mays, A.: Finite size corrections relating to distributions of the length of longest increasing subsequences. Adv. Appl. Math. 145, 102482 (2023)","journal-title":"Adv. Appl. Math."},{"key":"18_CR20","unstructured":"Frochaux, A., Kleest-Mei\u00dfner, S.: Puzzling over subsequence-query extensions: disjunction and generalised gaps. In: AMW 2023 of CEUR Workshop Proceedings, vol. 3409. CEUR-WS.org (2023)"},{"issue":"3","key":"18_CR21","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/s00453-014-9957-6","volume":"73","author":"T Gagie","year":"2015","unstructured":"Gagie, T., Hermelin, D., Landau, G.M., Weimann, O.: Binary jumbled pattern matching on trees and tree-like structures. Algorithmica 73(3), 571\u2013588 (2015)","journal-title":"Algorithmica"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Halfon, S., Schnoebelen, P., Zetzsche, G.: Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In:: LICS 2017, pp. 1\u201312. IEEE Computer Society (2017)","DOI":"10.1109\/LICS.2017.8005141"},{"issue":"1","key":"18_CR23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(91)90170-7","volume":"82","author":"J-J H\u00e9brard","year":"1991","unstructured":"H\u00e9brard, J.-J.: An algorithm for distinguishing efficiently bit-strings by their subsequences. Theor. Comput. Sci. 82(1), 35\u201349 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"18_CR24","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1016\/j.ipl.2014.11.008","volume":"115","author":"P Karandikar","year":"2015","unstructured":"Karandikar, P., Kufleitner, M., Schnoebelen, P.: On the index of Simon\u2019s congruence for piecewise testability. Inf. Process. Lett. 115(4), 515\u2013519 (2015)","journal-title":"Inf. Process. Lett."},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Karandikar, P., Schnoebelen, P.: The height of piecewise-testable languages and the complexity of the logic of subwords. Log. Methods Comput. Sci. 15(2) (2019)","DOI":"10.23638\/LMCS-15(2:6)2019"},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.tcs.2016.06.010","volume":"658","author":"J Karhum\u00e4ki","year":"2017","unstructured":"Karhum\u00e4ki, J., Puzynina, S., Rao, M., Whiteland, M.A.: On cardinalities of k-abelian equivalence classes. Theor. Comput. Sci. 658, 190\u2013204 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR27","doi-asserted-by":"publisher","first-page":"114078","DOI":"10.1016\/j.tcs.2023.114078","volume":"972","author":"S Kim","year":"2023","unstructured":"Kim, S., Han, Y.-S., Ko, S.-K., Salomaa, K.: On Simon\u2019s congruence closure of a string. Theor. Comput. Sci. 972, 114078 (2023)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR28","doi-asserted-by":"crossref","unstructured":"Kim, S., Han, Y.-S., Ko, S.-K., Salomaa, K.: On the Simon\u2019s congruence neighborhood of languages. In: DLT. LNCS, vol. 13911, pp. 168\u2013181. Springer (2023)","DOI":"10.1007\/978-3-031-33264-7_14"},{"key":"18_CR29","doi-asserted-by":"publisher","first-page":"114478","DOI":"10.1016\/j.tcs.2024.114478","volume":"994","author":"S Kim","year":"2024","unstructured":"Kim, S., Ko, S.-K., Han, Y.-S.: Simon\u2019s congruence pattern matching. Theor. Comput. Sci. 994, 114478 (2024)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR30","unstructured":"Kleest-Mei\u00dfner, S., Sattler, R., Schmid, M.L., Schweikardt, N., Weidlich, M.: Discovering event queries from traces: laying foundations for subsequence-queries with wildcards and gap-size constraints. In: ICDT. LIPIcs, vol. 220, pp. 18:1\u201318:21 (2022)"},{"key":"18_CR31","unstructured":"Kleest-Mei\u00dfner, S., Sattler, R., Schmid, M.L., Schweikardt, N., Weidlich, M.: Discovering multi-dimensional subsequence queries from traces - from theory to practice. In: BTW. LNI, vol. P-331, pp. 511\u2013533 (2023)"},{"issue":"3\u20134","key":"18_CR32","first-page":"199","volume":"189","author":"M Kosche","year":"2022","unstructured":"Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Absent subsequences in words. Fundam. Inf. 189(3\u20134), 199\u2013240 (2022)","journal-title":"Fundam. Inf."},{"key":"18_CR33","doi-asserted-by":"crossref","unstructured":"Kruskal, J.B.: The theory of well-quasi-ordering: a frequently discovered concept. J. Comb. Theory, Ser. A 13(3), 297\u2013305 (1972)","DOI":"10.1016\/0097-3165(72)90063-5"},{"key":"18_CR34","doi-asserted-by":"crossref","unstructured":"Kuske, D.: The subtrace order and counting first-order logic. In: CSR, pp. 289\u2013302. Springer (2020)","DOI":"10.1007\/978-3-030-50026-9_21"},{"key":"18_CR35","doi-asserted-by":"crossref","unstructured":"Kuske, D., Zetzsche, G.: Languages ordered by the subword order. In: FoSSaCS, pp. 348\u2013364. Springer (2019)","DOI":"10.1007\/978-3-030-17127-8_20"},{"key":"18_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","volume-title":"Combinatorics on Words","author":"M Lothaire","year":"1997","unstructured":"Lothaire, M.: Combinatorics on Words. Cambridge University Press, Cambridge Mathematical Library (1997)"},{"issue":"2","key":"18_CR37","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322\u2013336 (1978)","journal-title":"J. ACM"},{"key":"18_CR38","doi-asserted-by":"crossref","unstructured":"Manuch, J.: Characterization of a word by its subwords. In: DLT 1999, pp. 210\u2013219. World Scientific (1999)","DOI":"10.1142\/9789812792464_0018"},{"issue":"1","key":"18_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2003.04.001","volume":"68","author":"A Mateescu","year":"2004","unstructured":"Mateescu, A., Salomaa, A., Yu, S.: Subword histories and Parikh matrices. J. Comput. Syst. Sci. 68(1), 1\u201321 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"18_CR40","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R Parikh","year":"1966","unstructured":"Parikh, R.: On context-free languages. J. ACM 13(4), 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"18_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-030-28796-2_2","volume-title":"Combinatorics on Words","author":"S Puzynina","year":"2019","unstructured":"Puzynina, S.: Abelian properties of words. In: Merca\u015f, R., Reidenbach, D. (eds.) WORDS 2019. LNCS, vol. 11682, pp. 28\u201345. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-28796-2_2"},{"key":"18_CR42","first-page":"165","volume":"81","author":"A Salomaa","year":"2003","unstructured":"Salomaa, A.: Counting (scattered) subwords. Bull. EA Theor. Comput. Sci. 81, 165\u2013179 (2003)","journal-title":"Bull. EA Theor. Comput. Sci."},{"key":"18_CR43","doi-asserted-by":"crossref","unstructured":"Sattler, R., Kleest-Mei\u00dfner, S., Lange, S., Schmid, M.L., Schweikardt, N., Weidlich, M.: Disces: systematic discovery of event stream queries. Proc. ACM Manag. Data 3(1) (2025)","DOI":"10.1145\/3709682"},{"key":"18_CR44","doi-asserted-by":"crossref","unstructured":"Schnoebelen, P., Veron, J.: On arch factorization and subword universality for words and compressed words. In: WORDS 2023. LNCS, vol. 13899, pp. 274\u2013287. Springer (2023)","DOI":"10.1007\/978-3-031-33180-0_21"},{"key":"18_CR45","unstructured":"Simon, I.: Hierarchies of events with dot-depth one, PhD thesis, University of Waterloo (1972)"},{"key":"18_CR46","doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: AFL, 2nd GI Conference, Kaiserslautern, May 20-23, 1975. LNCS, vol. 33, pp. 214\u2013222. Springer (1975)","DOI":"10.1007\/3-540-07407-4_23"},{"key":"18_CR47","doi-asserted-by":"crossref","unstructured":"Tron\u00edcek, Z.: On problems related to absent subsequences. In: COCOA 2023. LNCS, vol. 14462, pp. 351\u2013363. Springer (2023)","DOI":"10.1007\/978-3-031-49614-1_26"},{"issue":"1","key":"18_CR48","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974)","journal-title":"J. ACM"},{"key":"18_CR49","doi-asserted-by":"crossref","unstructured":"Wang, C., Cho, K., Gu, J.: Neural machine translation with byte-level subwords. In: EAAI 2020, pp. 9154\u20139160. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i05.6451"},{"key":"18_CR50","unstructured":"Zetzsche, G.: The complexity of downward closure comparisons. In: ICALP 2016. LIPIcs, vol. 55, pp. 123:1\u2013123:14. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2016)"}],"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_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T19:28:10Z","timestamp":1785180490000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01475-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,17]]},"ISBN":["9783032014740","9783032014757"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01475-7_18","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"}}]}}