{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T11:15:49Z","timestamp":1775042149950,"version":"3.50.1"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100017142","name":"Gruppo Nazionale per il Calcolo Scientifico","doi-asserted-by":"publisher","award":["CUP_E53C24001950001"],"award-info":[{"award-number":["CUP_E53C24001950001"]}],"id":[{"id":"10.13039\/100017142","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2022TS4Y3N,# PNC0000007"],"award-info":[{"award-number":["2022TS4Y3N,# PNC0000007"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["956229,872539"],"award-info":[{"award-number":["956229,872539"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["20229BCXNW25"],"award-info":[{"award-number":["20229BCXNW25"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100031478","name":"NextGenerationEU","doi-asserted-by":"publisher","award":["ECS00000017"],"award-info":[{"award-number":["ECS00000017"]}],"id":[{"id":"10.13039\/100031478","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n Let\n \n \n $$\\varvec{\\textsf {Substr}}_{\\varvec{k}}\\varvec{(X)}$$<\/jats:tex-math>\n \n \n \n \n Substr<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n denote the set of length-\n \n \n $$\\varvec{k}$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n substrings of a given string\n \n \n $$\\varvec{X}$$<\/jats:tex-math>\n \n \n X<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for a given integer\n \n \n $$\\varvec{k}>\\varvec{0}$$<\/jats:tex-math>\n \n \n \n k<\/mml:mi>\n <\/mml:mrow>\n ><\/mml:mo>\n \n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We study the following basic string problem, called\n \n \n $$\\varvec{z}$$<\/jats:tex-math>\n \n \n z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Shortest<\/jats:sc>\n \n \n $$\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Equivalent Strings<\/jats:sc>\n : Given a set\n \n \n $$\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of\n \n \n $$\\varvec{n}$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n length-\n \n \n $$\\varvec{k}$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n strings and an integer\n \n \n $$\\varvec{z}>\\varvec{0}$$<\/jats:tex-math>\n \n \n \n z<\/mml:mi>\n <\/mml:mrow>\n ><\/mml:mo>\n \n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , list\n \n \n $$\\varvec{z}$$<\/jats:tex-math>\n \n \n z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n shortest distinct strings\n \n \n $$\\varvec{T}_{\\varvec{1}}\\varvec{,\\ldots ,}\\varvec{T}_{\\varvec{z}}$$<\/jats:tex-math>\n \n \n \n \n T<\/mml:mi>\n <\/mml:mrow>\n \n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n <\/mml:mrow>\n \n \n T<\/mml:mi>\n <\/mml:mrow>\n \n z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n such that\n \n \n $$\\varvec{\\textsf {Substr}}_{\\varvec{k}}\\varvec{(}\\varvec{T}_{\\varvec{i}}\\varvec{)}=\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n \n Substr<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n \n T<\/mml:mi>\n <\/mml:mrow>\n \n i<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , for all\n \n \n $$\\varvec{i}\\,{\\in }\\,\\varvec{[1,z]}$$<\/jats:tex-math>\n \n \n \n i<\/mml:mi>\n <\/mml:mrow>\n \n \u2208<\/mml:mo>\n \n \n [<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n z<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The\n \n \n $$\\varvec{z}$$<\/jats:tex-math>\n \n \n z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Shortest<\/jats:sc>\n \n \n $$\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Equivalent Strings<\/jats:sc>\n problem arises naturally as an encoding problem in many real-world applications; e.g. in data privacy, data compression, and bioinformatics. The\n \n \n $$\\varvec{1}$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Shortest<\/jats:sc>\n \n \n $$\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -Equivalent Strings<\/jats:sc>\n , referred to as\n Shortest<\/jats:sc>\n \n \n $$\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Equivalent String<\/jats:sc>\n , asks for a shortest string\n \n \n $$\\varvec{X}$$<\/jats:tex-math>\n \n \n X<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n such that\n \n \n $$\\varvec{\\textsf {Substr}}_{\\varvec{k}}\\varvec{(X)}=\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n \n Substr<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Our main contributions are as follows. Given a directed graph\n \n \n $$\\varvec{G}=\\varvec{(V,E)}$$<\/jats:tex-math>\n \n \n \n G<\/mml:mi>\n <\/mml:mrow>\n =<\/mml:mo>\n \n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , the\n Directed Chinese Postman<\/jats:sc>\n (DCP) problem asks for a shortest closed walk that visits every edge of\n \n \n $$\\varvec{G}$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n at least once. DCP can be solved using an algorithm for min-cost flow. We show, via a non-trivial reduction, that if\n Shortest<\/jats:sc>\n \n \n $$\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Equivalent String<\/jats:sc>\n over a\n binary alphabet<\/jats:italic>\n has a near-linear-time solution then so does DCP. Secondly, we show that the length of a shortest string output by\n Shortest<\/jats:sc>\n \n \n $$\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Equivalent String<\/jats:sc>\n is in\n \n \n $$\\varvec{\\mathcal {O}}\\varvec{(}\\varvec{k}+\\varvec{n}^{\\varvec{2}}\\varvec{)}$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We generalize this bound by showing that the total length of\n \n \n $$\\varvec{z}$$<\/jats:tex-math>\n \n \n z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n shortest strings is in\n \n \n $$\\varvec{\\mathcal {O}}\\varvec{(}\\varvec{zk}+\\varvec{zn}^{\\varvec{2}}+\\varvec{z}^{\\varvec{2}}\\varvec{n}\\varvec{)}$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n zk<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \n zn<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n +<\/mml:mo>\n \n \n z<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n n<\/mml:mi>\n <\/mml:mrow>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We derive these upper bounds by showing (asymptotically tight) bounds on the total length of\n \n \n $$\\varvec{z}$$<\/jats:tex-math>\n \n \n z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n shortest Eulerian walks in general directed graphs. Furthermore, we present an algorithm for solving\n \n \n $$\\varvec{z}$$<\/jats:tex-math>\n \n \n z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Shortest<\/jats:sc>\n \n \n $$\\varvec{\\mathcal {S}}_{\\varvec{k}}$$<\/jats:tex-math>\n \n \n \n S<\/mml:mi>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -\n Equivalent Strings<\/jats:sc>\n in\n \n \n $$\\varvec{\\mathcal {O}}\\varvec{(}\\varvec{nk}+\\varvec{n}^{\\varvec{2}}\\,\\varvec{\\log }^{\\varvec{2}}\\,\\varvec{n}+\\varvec{zn}^{\\varvec{2}}\\,\\varvec{\\log }\\,\\varvec{n}+|\\varvec{\\textsf {output}}|)$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n nk<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n \n log<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \n zn<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n log<\/mml:mo>\n <\/mml:mrow>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n \n |<\/mml:mo>\n \n output<\/mml:mi>\n <\/mml:mrow>\n |<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n time. If\n \n \n $$\\varvec{z}=\\varvec{1}$$<\/jats:tex-math>\n \n \n \n z<\/mml:mi>\n <\/mml:mrow>\n =<\/mml:mo>\n \n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , the time becomes\n \n \n $$\\varvec{\\mathcal {O}}\\varvec{(}\\varvec{nk}+\\varvec{n}^{\\varvec{2}}\\,\\varvec{\\log }^{\\varvec{2}}\\,\\varvec{n}\\varvec{)}$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n nk<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n \n log<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n by the fact that the size of the input is\n \n \n $$\\varvec{\\Theta }\\varvec{(nk)}$$<\/jats:tex-math>\n \n \n \n \u0398<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n n<\/mml:mi>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and the size of the output is\n \n \n $$\\varvec{\\mathcal {O}}\\varvec{(}\\varvec{k}+\\varvec{n}^{\\varvec{2}}\\varvec{)}$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n k<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Finally, we also provide a direct technical application of our algorithms on strings in an existing data privacy framework. A preliminary version of this paper was announced at CPM 2022.\n <\/jats:p>","DOI":"10.1007\/s00224-025-10240-z","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T09:33:25Z","timestamp":1775036005000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Strings Having the Same Length-k Substrings"],"prefix":"10.1007","volume":"70","author":[{"given":"Giulia","family":"Bernardini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessio","family":"Conte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Esteban","family":"Gabory","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grigorios","family":"Loukides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giulia","family":"Punzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michelle","family":"Sweering","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,1]]},"reference":[{"key":"10240_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, Cambridge (2007)"},{"key":"10240_CR2","first-page":"1","volume-title":"String Processing and Information Retrieval","author":"JN Alanko","year":"2023","unstructured":"Alanko, J.N., Biagi, E., Puglisi, S.J.: Longest common prefix arrays for succinct k-spectra. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds.) String Processing and Information Retrieval, pp. 1\u201313. Springer, Cham (2023)"},{"issue":"1","key":"10240_CR3","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"JR Edmonds","year":"1973","unstructured":"Edmonds, J.R., Johnson, E.L.: Matching, Euler tours and the Chinese Postman. Math. Program. 5(1), 88\u2013124 (1973). https:\/\/doi.org\/10.1007\/BF01580113","journal-title":"Math. Program."},{"key":"10240_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02614365","volume":"77","author":"JB Orlin","year":"1997","unstructured":"Orlin, J.B.: A polynomial time primal network simplex algorithm for minimum cost flows. Math. Program. 77, 109\u2013129 (1997). https:\/\/doi.org\/10.1007\/BF02614365","journal-title":"Math. Program."},{"key":"10240_CR5","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02614369","volume":"77","author":"RE Tarjan","year":"1997","unstructured":"Tarjan, R.E.: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program. 77, 169\u2013177 (1997). https:\/\/doi.org\/10.1007\/BF02614369","journal-title":"Math. Program."},{"issue":"12","key":"10240_CR6","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1145\/3610940","volume":"66","author":"L Chen","year":"2023","unstructured":"Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sachdeva, S.: Almost-linear-time algorithms for maximum flow and minimum-cost flow. Commun. ACM 66(12), 85\u201392 (2023). https:\/\/doi.org\/10.1145\/3610940","journal-title":"Commun. ACM"},{"key":"10240_CR7","first-page":"241","volume":"7","author":"JP Hutchinson","year":"1975","unstructured":"Hutchinson, J.P.: On words with prescribed overlapping subsequences. Util. Math. 7, 241\u2013250 (1975)","journal-title":"Util. Math."},{"issue":"1","key":"10240_CR8","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0097-3165(75)90068-0","volume":"18","author":"JP Hutchinson","year":"1975","unstructured":"Hutchinson, J.P., Wilf, H.S.: On Eulerian circuits and words with prescribed adjacency patterns. J. Comb. Theory Ser. A 18(1), 80\u201387 (1975). https:\/\/doi.org\/10.1016\/0097-3165(75)90068-0","journal-title":"J. Comb. Theory Ser. A"},{"key":"10240_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1186\/1471-2105-11-21","volume":"11","author":"C Kingsford","year":"2010","unstructured":"Kingsford, C., Schatz, M.C., Pop, M.: Assembly complexity of prokaryotic genomes using short reads. BMC Bioinform. 11, 21 (2010). https:\/\/doi.org\/10.1186\/1471-2105-11-21","journal-title":"BMC Bioinform."},{"key":"10240_CR10","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Chen, H., Fici, G., Loukides, G., Pissis, S.P.: Reverse-safe text indexing. ACM J. Exp. Algorithmics 26 (2021). https:\/\/doi.org\/10.1145\/3461698","DOI":"10.1145\/3461698"},{"key":"10240_CR11","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-0-8176-4842-8_12","volume-title":"Classic Papers in Combinatorics","author":"T Aardenne-Ehrenfest","year":"1987","unstructured":"Aardenne-Ehrenfest, T., Bruijn, N.G.: Circuits and trees in oriented linear graphs. In: Gessel, I., Rota, G.-C. (eds.) Classic Papers in Combinatorics, pp. 149\u2013163. Birkh\u00e4user Boston, Boston, MA (1987). https:\/\/doi.org\/10.1007\/978-0-8176-4842-8_12"},{"key":"10240_CR12","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). https:\/\/doi.org\/10.1016\/j.tcs.2016.06.010","journal-title":"Theor. Comput. Sci."},{"key":"10240_CR13","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-030-86593-1_11","volume-title":"Fundamentals of Computation Theory","author":"A Conte","year":"2021","unstructured":"Conte, A., Grossi, R., Loukides, G., Pisanti, N., Pissis, S.P., Punzi, G.: Beyond the best theorem: Fast assessment of eulerian trails. In: Bampis, E., Pagourtzis, A. (eds.) Fundamentals of Computation Theory, pp. 162\u2013175. Springer, Cham (2021)"},{"key":"10240_CR14","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Chen, H., Fici, G., Loukides, G., Pissis, S.P.: Reverse-safe data structures for text indexing. In: Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX, pp. 199\u2013213 (2020). https:\/\/doi.org\/10.1137\/1.9781611976007.16","DOI":"10.1137\/1.9781611976007.16"},{"issue":"1","key":"10240_CR15","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s00453-014-9936-y","volume":"74","author":"A Orlandi","year":"2016","unstructured":"Orlandi, A., Venturini, R.: Space-efficient substring occurrence estimation. Algorithmica 74(1), 65\u201390 (2016). https:\/\/doi.org\/10.1007\/s00453-014-9936-y","journal-title":"Algorithmica"},{"issue":"17","key":"10240_CR16","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"PA Pevzner","year":"2001","unstructured":"Pevzner, P.A., Tang, H., Waterman, M.S.: An Eulerian path approach to DNA fragment assembly. Proc. Natl. Acad. Sci. 98(17), 9748\u20139753 (2001). https:\/\/doi.org\/10.1073\/pnas.171285098","journal-title":"Proc. Natl. Acad. Sci."},{"key":"10240_CR17","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Marchetti-Spaccamela, A., Pissis, S.P., Stougie, L., Sweering, M.: Constructing strings avoiding forbidden substrings. In: 32nd Annual Symposium on Combinatorial Pattern Matching (CPM). LIPIcs, vol. 191, pp. 9\u20131918. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2021). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2021.9","DOI":"10.4230\/LIPICS.CPM.2021.9"},{"key":"10240_CR18","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Conte, A., Gabory, E., Grossi, R., Loukides, G., Pissis, S.P., Punzi, G., Sweering, M.: On strings having the same length- k substrings. In: 33rd Annual Symposium on Combinatorial Pattern Matching (CPM). LIPIcs, vol. 223, pp. 16\u201311617. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2022). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2022.16","DOI":"10.4230\/LIPICS.CPM.2022.16"},{"key":"10240_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-021-02297-z","volume":"22","author":"K B\u0159inda","year":"2021","unstructured":"B\u0159inda, K., Baym, M., Kucherov, G.: Simplitigs as an efficient and scalable representation of de Bruijn graphs. Genome Biol. 22, 1\u201324 (2021). https:\/\/doi.org\/10.1186\/s13059-021-02297-z","journal-title":"Genome Biol."},{"issue":"1","key":"10240_CR20","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1186\/S13015-023-00227-1","volume":"18","author":"SS Schmidt","year":"2023","unstructured":"Schmidt, S.S., Alanko, J.N.: Eulertigs: Minimum plain text representation of k-mer sets without repetitions in linear time. Algorithms Mol. Biol. 18(1), 5 (2023). https:\/\/doi.org\/10.1186\/S13015-023-00227-1","journal-title":"Algorithms Mol. Biol."},{"issue":"4","key":"10240_CR21","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1089\/CMB.2020.0431","volume":"28","author":"A Rahman","year":"2021","unstructured":"Rahman, A., Medevedev, P.: Representation of k-mer sets using spectrum-preserving string sets. J. Comput. Biol. 28(4), 381\u2013394 (2021). https:\/\/doi.org\/10.1089\/CMB.2020.0431","journal-title":"J. Comput. Biol."},{"issue":"1","key":"10240_CR22","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1186\/s13059-023-02968-z","volume":"24","author":"S Schmidt","year":"2023","unstructured":"Schmidt, S., Khan, S., Alanko, J.N., Pibiri, G.E., Tomescu, A.I.: Matchtigs: Minimum plain text representation of k-mer sets. Genome Biol. 24(1), 136 (2023). https:\/\/doi.org\/10.1186\/s13059-023-02968-z","journal-title":"Genome Biol."},{"key":"10240_CR23","unstructured":"Sladk\u1ef3, O., Vesel\u1ef3, P., B\u0159inda, K.: Masked superstrings as a unified framework for textual k-mer set representations. bioRxiv, 2023\u201302 (2023)"},{"key":"10240_CR24","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Chen, H., G\u00f8rtz, I.L., Krogh, C., Loukides, G., Pissis, S.P., Stougie, L., Sweering, M.: Connecting de bruijn graphs. In: 35th Annual Symposium on Combinatorial Pattern Matching (CPM). LIPIcs, vol. 296, pp. 6\u20131616. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2024). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2024.6","DOI":"10.4230\/LIPICS.CPM.2024.6"},{"key":"10240_CR25","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Chen, H., Loukides, G., Pissis, S.P., Stougie, L., Sweering, M.: Making de Bruijn graphs Eulerian. In: 33rd Annual Symposium on Combinatorial Pattern Matching (CPM). LIPIcs, vol. 223, pp. 12\u201311218. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2022). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.12","DOI":"10.4230\/LIPIcs.CPM.2022.12"},{"issue":"6","key":"10240_CR26","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1089\/CMB.2024.0530","volume":"31","author":"E Rossignolo","year":"2024","unstructured":"Rossignolo, E., Comin, M.: Enhanced compression of k-mer sets with counters via de bruijn graphs. J. Comput. Biol. 31(6), 524\u2013538 (2024). https:\/\/doi.org\/10.1089\/CMB.2024.0530","journal-title":"J. Comput. Biol."},{"issue":"2","key":"10240_CR27","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/S10618-024-01074-3","volume":"39","author":"G Bernardini","year":"2025","unstructured":"Bernardini, G., Liu, C., Loukides, G., Marchetti-Spaccamela, A., Pissis, S.P., Stougie, L., Sweering, M.: Missing value replacement in strings and applications. Data Min. Knowl. Discov. 39(2), 12 (2025). https:\/\/doi.org\/10.1007\/S10618-024-01074-3","journal-title":"Data Min. Knowl. Discov."},{"key":"10240_CR28","doi-asserted-by":"publisher","unstructured":"Simon, I.: Piecewise testable events. In: Automata Theory and Formal Languages, 2nd GI Conference. Lecture Notes in Computer Science, vol. 33, pp. 214\u2013222. Springer, Berlin, Heidelberg (1975). https:\/\/doi.org\/10.1007\/3-540-07407-4_23","DOI":"10.1007\/3-540-07407-4_23"},{"key":"10240_CR29","doi-asserted-by":"publisher","unstructured":"Lothaire, M.: Combinatorics on Words, 2nd edn. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997). https:\/\/doi.org\/10.1017\/CBO9780511566097","DOI":"10.1017\/CBO9780511566097"},{"key":"10240_CR30","doi-asserted-by":"publisher","unstructured":"Karandikar, P., Schnoebelen, P.: The height of piecewise-testable languages with applications in logical complexity. In: 25th EACSL Annual Conference on Computer Science Logic. LIPIcs, vol. 62, pp. 37\u201313722. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2016.37","DOI":"10.4230\/LIPIcs.CSL.2016.37"},{"issue":"4","key":"10240_CR31","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). https:\/\/doi.org\/10.1016\/j.ipl.2014.11.008","journal-title":"Inf. Process. Lett."},{"key":"10240_CR32","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.23638\/LMCS-15(2:6)2019","DOI":"10.23638\/LMCS-15(2:6)2019"},{"key":"10240_CR33","doi-asserted-by":"publisher","unstructured":"Barker, L., Fleischmann, P., Harwardt, K., Manea, F., Nowotka, D.: Scattered factor-universality of words. In: Developments in Language Theory - 24th International Conference. Lecture Notes in Computer Science, vol. 12086, pp. 14\u201328. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-48516-0_2","DOI":"10.1007\/978-3-030-48516-0_2"},{"key":"10240_CR34","doi-asserted-by":"publisher","unstructured":"Kim, S., Han, Y., Ko, S., Salomaa, K.: On the Simon\u2019s congruence neighborhood of languages. In: 27th International Conference on Developments in Language Theory (DLT). Lecture Notes in Computer Science, vol. 13911, pp. 168\u2013181. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-33264-7_14","DOI":"10.1007\/978-3-031-33264-7_14"},{"issue":"1","key":"10240_CR35","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(91)90170-7","volume":"82","author":"J H\u00e9brard","year":"1991","unstructured":"H\u00e9brard, J.: An algorithm for distinguishing efficiently bit-strings by their subsequences. Theor. Comput. Sci. 82(1), 35\u201349 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90170-7","journal-title":"Theor. Comput. Sci."},{"key":"10240_CR36","doi-asserted-by":"publisher","unstructured":"Garel, E.: Minimal separators of two words. In: 4th Annual Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 684, pp. 35\u201353. Springer, Berlin, Heidelberg (1993). https:\/\/doi.org\/10.1007\/BFb0029795","DOI":"10.1007\/BFb0029795"},{"key":"10240_CR37","doi-asserted-by":"publisher","unstructured":"Tron\u00edcek, Z.: Common subsequence automaton. In: Implementation and Application of Automata, 7th International Conference. Lecture Notes in Computer Science, vol. 2608, pp. 270\u2013275. Springer, Berlin, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-44977-9_28","DOI":"10.1007\/3-540-44977-9_28"},{"issue":"3\u20134","key":"10240_CR38","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S1570-8667(03)00029-7","volume":"1","author":"M Crochemore","year":"2003","unstructured":"Crochemore, M., Melichar, B., Tron\u00edcek, Z.: Directed acyclic subsequence graph - overview. J. Discrete Algorithms 1(3\u20134), 255\u2013280 (2003). https:\/\/doi.org\/10.1016\/S1570-8667(03)00029-7","journal-title":"J. Discrete Algorithms"},{"key":"10240_CR39","doi-asserted-by":"publisher","unstructured":"Fleischer, L., Kufleitner, M.: Testing Simon\u2019s congruence. In: 43rd International Symposium on Mathematical Foundations of Computer Science. LIPIcs, vol. 117, pp. 62\u201316213. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.62","DOI":"10.4230\/LIPIcs.MFCS.2018.62"},{"key":"10240_CR40","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Kosche, M., Ko\u00df, T., Manea, F., Siemer, S.: Efficiently testing Simon\u2019s congruence. In: 38th International Symposium on Theoretical Aspects of Computer Science (STAC). LIPIcs, vol. 187, pp. 34\u201313418. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.34","DOI":"10.4230\/LIPIcs.STACS.2021.34"},{"key":"10240_CR41","doi-asserted-by":"publisher","unstructured":"Kim, S., Ko, S., Han, Y.: Simon\u2019s congruence pattern matching. In: 33rd International Symposium on Algorithms and Computation (ISAAC). LIPIcs, vol. 248, pp. 60\u201316017. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2022). https:\/\/doi.org\/10.4230\/LIPICS.ISAAC.2022.60","DOI":"10.4230\/LIPICS.ISAAC.2022.60"},{"key":"10240_CR42","doi-asserted-by":"publisher","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: Reachability Problems - 17th International Conference (RP). Lecture Notes in Computer Science, vol. 14235, pp. 155\u2013170. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-45286-4_12","DOI":"10.1007\/978-3-031-45286-4_12"},{"key":"10240_CR43","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., Han, Y.: Simon\u2019s congruence pattern matching. Theor. Comput. Sci. 994, 114478 (2024). https:\/\/doi.org\/10.1016\/J.TCS.2024.114478","journal-title":"Theor. Comput. Sci."},{"key":"10240_CR44","first-page":"15","volume":"53","author":"L Euler","year":"1741","unstructured":"Euler, L.: Solutio problematis ad geometriam situs pertinentis. Euler Archive - All Works 53, 15 (1741)","journal-title":"Euler Archive - All Works"},{"key":"10240_CR45","doi-asserted-by":"publisher","unstructured":"Goldberg, A.V., Tarjan, R.E.: Solving minimum-cost flow problems by successive approximation. In: Aho, A.V. (ed.) Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 7\u201318. ACM, New York (1987). https:\/\/doi.org\/10.1145\/28395.28397","DOI":"10.1145\/28395.28397"},{"issue":"2","key":"10240_CR46","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1287\/opre.41.2.338","volume":"41","author":"JB Orlin","year":"1993","unstructured":"Orlin, J.B.: A faster strongly polynomial minimum cost flow algorithm. Oper. Res. 41(2), 338\u2013350 (1993). https:\/\/doi.org\/10.1287\/opre.41.2.338","journal-title":"Oper. Res."},{"key":"10240_CR47","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/J.DAM.2022.07.007","volume":"321","author":"D K\u00f6nen","year":"2022","unstructured":"K\u00f6nen, D., Schmidt, D.R., Spisla, C.: Finding all minimum cost flows and a faster algorithm for the K best flow problem. Discret. Appl. Math. 321, 333\u2013349 (2022). https:\/\/doi.org\/10.1016\/J.DAM.2022.07.007","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"10240_CR48","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF02099691","volume":"57","author":"HW Hamacher","year":"1995","unstructured":"Hamacher, H.W.: A note on K best network flows. Ann. Oper. Res. 57(1), 65\u201372 (1995). https:\/\/doi.org\/10.1007\/BF02099691","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"10240_CR49","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1016\/j.cor.2012.08.014","volume":"40","author":"A Sede\u00f1o-Noda","year":"2013","unstructured":"Sede\u00f1o-Noda, A., Espino-Mart\u00edn, J.J.: On the K best integer network flows. Comput. Oper. Res. 40(2), 616\u2013626 (2013). https:\/\/doi.org\/10.1016\/j.cor.2012.08.014","journal-title":"Comput. Oper. Res."},{"key":"10240_CR50","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.jcss.2016.06.008","volume":"104","author":"B Cazaux","year":"2019","unstructured":"Cazaux, B., Lecroq, T., Rivals, E.: Linking indexing data structures to de Bruijn graphs: Construction and update. J. Comput. Syst. Sci. 104, 165\u2013183 (2019). https:\/\/doi.org\/10.1016\/j.jcss.2016.06.008","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"10240_CR51","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1142\/S0218488502001648","volume":"10","author":"L Sweeney","year":"2002","unstructured":"Sweeney, L.: k-Anonymity: A model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 10(5), 557\u2013570 (2002). https:\/\/doi.org\/10.1142\/S0218488502001648","journal-title":"Int. J. Uncertain. Fuzziness Knowl. Based Syst."},{"issue":"5","key":"10240_CR52","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1142\/S021848850200165X","volume":"10","author":"L Sweeney","year":"2002","unstructured":"Sweeney, L.: Achieving k-Anonymity privacy protection using generalization and suppression. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 10(5), 571\u2013588 (2002). https:\/\/doi.org\/10.1142\/S021848850200165X","journal-title":"Int. J. Uncertain. Fuzziness Knowl. Based Syst."},{"issue":"1","key":"10240_CR53","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/BF01442866","volume":"6","author":"C Hierholzer","year":"1873","unstructured":"Hierholzer, C., Wiener, C.: \u00dcber die m\u00f6glichkeit, einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren. Math. Ann. 6(1), 30\u201332 (1873)","journal-title":"Math. Ann."},{"key":"10240_CR54","unstructured":"Biggs, N.L., Lloyd, E.K., Wilson, R.J.: Graph Theory 1736-1936. Clarendon Press, Oxford (1976). Chap. 1B"},{"key":"10240_CR55","doi-asserted-by":"publisher","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, pp. 1\u201311. IEEE Computer Society, Iowa (1973). https:\/\/doi.org\/10.1109\/SWAT.1973.13","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10240-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10240-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10240-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T09:33:29Z","timestamp":1775036009000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10240-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,1]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10240"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10240-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,1]]},"assertion":[{"value":"31 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"21"}}