Absent subsequences in words

• Autorzy: Kosche Maria , Koß Tore , Manea Florin , Siemer Stefan

Identyfikatory

DOI

10.3233/FI-222159

• Języki publikacji: EN

Abstrakty

EN

An absent factor of a string w is a string u which does not occur as a contiguous substring (a.k.a. factor) inside w. We extend this well-studied notion and define absent subsequences: a string u is an absent subsequence of a string w if u does not occur as subsequence (a.k.a. scattered factor) inside w. Of particular interest to us are minimal absent subsequences, i.e., absent subsequences whose every subsequence is not absent, and shortest absent subsequences, i.e., absent subsequences of minimal length. We show a series of combinatorial and algorithmic results regarding these two notions. For instance: we give combinatorial characterisations of the sets of minimal and, respectively, shortest absent subsequences in a word, as well as compact representations of these sets; we show how we can test efficiently if a string is a shortest or minimal absent subsequence in a word, and we give efficient algorithms computing the lexicographically smallest absent subsequence of each kind; also, we show how a data structure for answering shortest absent subsequence-queries for the factors of a given string can be efficiently computed.

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2023
• Tom: Vol. 189, nr 3-4
• Strony: 199--240
• Opis fizyczny: Bibliogr. 123 poz., tab.

Twórcy

autor

Kosche Maria

• Institute for Computer Science Georg-August University Göttingen, Germany

autor

Koß Tore

• Institute for Computer Science Georg-August University Göttingen, Germany

autor

Manea Florin

• Institute for Computer Science Georg-August University Göttingen, Germany

autor

Siemer Stefan

• Institute for Computer Science Georg-August University Göttingen, Germany

Bibliografia

• [1] Sakarovitch J, Simon I. Subwords. In: Lothaire M (ed.), Combinatorics on Words, chapter 6, pp. 105-142. Cambridge University Press, 1997.
• [2] Halfon S, Schnoebelen P, Zetzsche G. Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In: Proc. LICS 2017. 2017 pp. 1-12. doi:10.48550/arXiv.1701.07470.
• [3] Karandikar P, Kufleitner M, Schnoebelen P. On the index of Simon’s congruence for piecewise testability. Inf. Process. Lett., 2015. 115(4):515-519. doi:10.1016/j.ipl.2014.11.008.
• [4] Karandikar P, Schnoebelen P. The Height of Piecewise-Testable Languages with Applications in Logical Complexity. In: Proc. CSL 2016, volume 62 of LIPIcs. 2016 pp. 37:1-37:22.
• [5] Karandikar P, Schnoebelen P. The height of piecewise-testable languages and the complexity of the logic of subwords. Log. Methods Comput. Sci., 2019. 15(2). doi:10.23638/LMCS-15(2:6)2019.
• [6] Kuske D. The Subtrace Order and Counting First-Order Logic. In: Proc. CSR 2020, volume 12159 of Lecture Notes in Computer Science. 2020 pp. 289-302. doi:10.1007/978-3-030-50026-9 21.
• [7] Kuske D, Zetzsche G. Languages Ordered by the Subword Order. In: Proc. FOSSACS 2019, volume 11425 of Lecture Notes in Computer Science. 2019 pp. 348-364. doi:10.1007/978-3-030-17127-8 20.
• [8] Simon I. Hierarchies of events with dot-depth one - Ph.D. thesis. University of Waterloo, 1972.
• [9] Simon I. Piecewise testable events. In: Autom. Theor. Form. Lang., 2nd GI Conf., volume 33 of LNCS. 1975 pp. 214-222.
• [10] Zetzsche G. The Complexity of Downward Closure Comparisons. In: Proc. ICALP 2016, volume 55 of LIPIcs. 2016 pp. 123:1-123:14. doi:10.48550/arXiv.1605.03149.
• [11] Freydenberger DD, Gawrychowski P, Karhum¨aki J, Manea F, Rytter W. Testing k-binomial equivalence. In: Multidisciplinary Creativity, a collection of papers dedicated to G. P˘aun 65th birthday. 2015 pp. 239-248. Available in CoRR. doi:10.48550/arXiv.1509.00622.
• [12] Lejeune M, Leroy J, Rigo M. Computing the k-binomial Complexity of the Thue-Morse Word. In: Proc. DLT 2019, volume 11647 of Lecture Notes in Computer Science. 2019 pp. 278-291. doi:10.1016/j.jcta.2020.105284.
• [13] Leroy J, Rigo M, Stipulanti M. Generalized Pascal triangle for binomial coefficients of words. Electron. J. Combin., 2017. 24(1.44):36 pp. doi:10.1016/j.aam.2016.04.006.
• [14] Mateescu A, Salomaa A, Yu S. Subword Histories and Parikh Matrices. J. Comput. Syst. Sci., 2004. 68(1):1-21. doi:10.1016/j.jcss.2003.04.001.
• [15] Rigo M, Salimov P. Another generalization of abelian equivalence: Binomial complexity of infinite words. Theor. Comput. Sci., 2015. 601:47-57. doi:10.1016/j.tcs.2015.07.025.
• [16] Salomaa A. Connections Between Subwords and Certain Matrix Mappings. Theoret. Comput. Sci., 2005. 340(2):188-203. doi:10.1016/j.tcs.2005.03.024.
• [17] Seki S. Absoluteness of subword inequality is undecidable. Theor. Comput. Sci., 2012. 418:116-120. doi:10.1016/j.tcs.2011.10.017.
• [18] Baeza-Yates RA. Searching Subsequences. Theor. Comput. Sci., 1991. 78(2):363-376.
• [19] Bringmann K, Chaudhury BR. Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. In: Proc. FSTTCS 2018, volume 122 of LIPIcs. 2018 pp. 40:1-40:16. doi:10.48550/arXiv.1810.01238.
• [20] Bringmann K, Künnemann M. Multivariate Fine-Grained Complexity of Longest Common Subsequence. In: Proc. SODA 2018. 2018 pp. 1216-1235. doi:10.1137/1.9781611975031.79.
• [21] Maier D. The Complexity of Some Problems on Subsequences and Supersequences. J. ACM, 1978. 25(2):322-336. doi:10.1145/322063.322075.
• [22] Wagner RA, Fischer MJ. The String-to-String Correction Problem. J. ACM, 1974. 21(1):168-173.
• [23] Sankoff D, Kruskal J. Time Warps, String Edits, and Macromolecules The Theory and Practice of Sequence Comparison. Cambridge University Press, 2000 (reprinted). Originally published in 1983. ISBN-10:1575862174, 13: 978-1575862170.
• [24] Pin J. The Consequences of Imre Simon’s Work in the Theory of Automata, Languages, and Semigroups. In: Proc. LATIN 2004, volume 2976 of Lecture Notes in Computer Science. 2004 p. 5. doi:10.1007/978-3-540-24698-5 4.
• [25] Pin J. The influence of Imre Simon’s work in the theory of automata, languages and semigroups. Semi group Forum, 2019. 98:1-8. doi:10.1007/s00233-019-09999-8.
• [26] Crochemore M, Melichar B, Tron´ıcek Z. Directed acyclic subsequence graph - Overview. J. Discrete Algorithms, 2003. 1(3-4):255-280. doi:10.1016/S1570-8667(03)00029-7.
• [27] Fleischer L, Kufleitner M. Testing Simon’s congruence. In: Proc. MFCS 2018, volume 117 of LIPIcs. 2018 pp. 62:1-62:13. doi:10.48550/arXiv.1804.10459.
• [28] Hebrard JJ. An algorithm for distinguishing efficiently bit-strings by their subsequences. Theoretical computer science, 1991. 82(1):35-49. doi:10.1016/0304-3975(91)90170-7.
• [29] Garel E. Minimal Separators of Two Words. In: Proc. CPM 1993, volume 684 of Lecture Notes in Computer Science. 1993 pp. 35-53. doi:10.1007/BFb0029795.
• [30] Simon I. Words distinguished by their subwords (extended Abstract). In: Proc. WORDS 2003, volume 27 of TUCS General Publication. 2003 pp. 6-13.
• [31] Tron´ıcek Z. Common Subsequence Automaton. In: Proc. CIAA 2002 (Revised Papers), volume 2608 of Lecture Notes in Computer Science. 2002 pp. 270-275. doi:10.1007/3-540-44977-9 28.
• [32] Barker L, Fleischmann P, Harwardt K, Manea F, Nowotka D. Scattered Factor-Universality of Words. In: Jonoska N, Savchuk D (eds.), Proc. DLT 2020, volume 12086 of Lecture Notes in Computer Science. 2020 pp. 14-28. doi:10.1007/978-3-030-48516-0 2.
• [33] Gawrychowski P, Kosche M, Koß T, Manea F, Siemer S. Efficiently Testing Simon’s Congruence. In: Bl¨aser M, Monmege B (eds.), 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbr¨ucken, Germany (Virtual Conference), volume 187 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2021 pp. 34:1-34:18. doi:10.4230/LIPIcs.STACS.2021.34.
• [34] Day JD, Fleischmann P, Kosche M, Koß T, Manea F, Siemer S. The Edit Distance to k-Subsequence Universality. In: Bl¨aser M, Monmege B (eds.), 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbr¨ucken, Germany (Virtual Conference), volume 187 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2021 pp. 25:1-25:19. doi:10.4230/LIPIcs.STACS.2021.25.
• [35] Barton C, Heliou A, Mouchard L, Pissis SP. Linear-time computation of minimal absent words using suffix array. BMC bioinformatics, 2014. 15(1):1-10. doi:10.1186/s12859-014-0388-9.
• [36] Chairungsee S, Crochemore M. Using minimal absent words to build phylogeny. Theoretical Computer Science, 2012. 450:109-116. doi:10.1016/j.tcs.2012.04.031.
• [37] Charalampopoulos P, Crochemore M, Fici G, Mercas¸ R, Pissis SP. Alignment-free sequence comparison using absent words. Information and Computation, 2018. 262:57-68. doi:10.1016/j.ic.2018.06.002.
• [38] Crochemore M, Mignosi F, Restivo A, Salemi S. Data compression using antidictionaries. Proceedings of the IEEE, 2000. 88(11):1756-1768. doi:10.1109/5.892711.
• [39] Pratas D, Silva JM. Persistent minimal sequences of SARS-CoV-2. Bioinformatics, 2020. doi:10.1093/bioinformatics/btaa686.
• [40] Silva RM, Pratas D, Castro L, Pinho AJ, Ferreira PJ. Three minimal sequences found in Ebola virus genomes and absent from human DNA. Bioinformatics, 2015. 31(15):2421-2425. doi:10.1093/bioinformatics/btv189.
• [41] Bernardini G, Marchetti-Spaccamela A, Pissis S, Stougie L, Sweering M. Constructing Strings Avoiding Forbidden Substrings. to appear, Proc. CPM 2021, 2021. doi:10.4230/LIPIcs.CPM.2021.9.
• [42] Crochemore M, Mignosi F, Restivo A. Automata and forbidden words. Information Processing Letters, 1998. 67(3):111-117. doi:10.1016/S0020-0190(98)00104-5.
• [43] Fici G, Gawrychowski P. Minimal absent words in rooted and unrooted trees. In: International Symposium on String Processing and Information Retrieval. Springer, 2019 pp. 152-161. doi:10.1007/978-3-030-32686-9 11.
• [44] Fici G, Mignosi F, Restivo A, Sciortino M. Word assembly through minimal forbidden words. Theoretical Computer Science, 2006. 359(1-3):214-230. doi:10.1016/j.tcs.2006.03.006.
• [45] Fici G, Restivo A, Rizzo L. Minimal forbidden factors of circular words. Theoretical Computer Science, 2019. 792:144-153. doi:10.1016/j.tcs.2018.05.037.
• [46] Nakashima Y, Inenaga S, Bannai H, Takeda M. Minimal Unique Substrings and Minimal Absent Words in a Sliding Window. In: SOFSEM 2020: Theory and Practice of Computer Science: 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020, Proceedings, volume 12011. Springer Nature, 2020 p. 148. doi:10.1007/978-3-030-38919-2 13.
• [47] Mignosi F, Restivo A, Sciortino M. Words and forbidden factors. Theoretical Computer Science, 2002. 273(1-2):99-117. doi:10.1016/S0304-3975(00)00436-9.
• [48] Ayad LA, Badkobeh G, Fici G, H´eliou A, Pissis SP. Constructing antidictionaries in output-sensitive space. In: 2019 Data Compression Conference (DCC). IEEE, 2019 pp. 538-547. doi:10.48550/arXiv.1902.04785.
• [49] Badkobeh G, Charalampopoulos P, Pissis S. Internal Shortest Absent Word Queries. to appear, Proc. CPM 2021, 2021. doi:10.48550/arXiv.2106.01763.
• [50] Barton C, H´eliou A, Mouchard L, Pissis SP. Parallelising the computation of minimal absent words. In: Parallel Processing and Applied Mathematics, pp. 243-253. Springer, 2016. doi:10.1007/978-3-319-32152-3 23.
• [51] Charalampopoulos P, Crochemore M, Pissis SP. On extended special factors of a word. In: International Symposium on String Processing and Information Retrieval. Springer, 2018 pp. 131-138. doi:10.1007/978-3-030-00479-8 11.
• [52] Crochemore M, H´eliou A, Kucherov G, Mouchard L, Pissis SP, Ramusat Y. Absent words in a sliding window with applications. Information and Computation, 2020. 270:104461. doi:10.1016/j.ic.2019.104461.
• [53] Fujishige Y, Tsujimaru Y, Inenaga S, Bannai H, Takeda M. Computing DAWGs and minimal absent words in linear time for integer alphabets. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPICS.MFCS.2016.38.
• [54] Kitaev S. Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2011. ISBN 978-3-642-17332-5. doi:10.1007/978-3-642-17333-2.
• [55] Crochemore M, Hancart C, Lecroq T. Algorithms on strings. Cambridge University Press, 2007. ISBN 978-0-521-84899-2.
• [56] Bender MA, Farach-Colton M. The Level Ancestor Problem simplified. Theor. Comput. Sci., 2004. 321(1):5-12. doi:10.1016/j.tcs.2003.05.002.
• [57] Ben-Amram AM. The Euler Path to Static Level-Ancestors. CoRR, 2009. abs/0909.1030. 0909.1030, URL http://arxiv.org/abs/0909.1030.
• [58] Sedgewick R, Wayne K. Algorithms, 4th Edition. Addison-Wesley, 2011. ISBN 978-0-321-57351-3.
• [59] Wasa K. Enumeration of Enumeration Algorithms. CoRR, 2016. abs/1605.05102. 1605.05102, URL http://arxiv.org/abs/1605.05102.
• [60] Bender MA, Farach-Colton M. The LCA Problem Revisited. In: Gonnet GH, Panario D, Viola A (eds.), LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, volume 1776 of Lecture Notes in Computer Science. Springer, 2000 pp. 88-94. doi:10.1007/10719839\ 9.
• [61] Kosche M, Koß T, Manea F, Siemer S. Absent Subsequences in Words. In: Bell PC, Totzke P, Potapov I (eds.), Reachability Problems - 15th International Conference, RP 2021, Liverpool, UK, October 25-27, 2021, Proceedings, volume 13035 of Lecture Notes in Computer Science. Springer, 2021 pp. 115-131. doi:10.1007/978-3-030-89716-1\ 8. URL https://doi.org/10.1007/978-3-030-89716-1_8
• [62] Garcia SP, Pinho AJ, Rodrigues JM, Bastos CA, Ferreira PJ. Minimal absent words in prokaryotic and eukaryotic genomes. PLoS One, 2011. 6(1):e16065.
• [63] Ota T, Morita H. On the adaptive antidictionary code using minimal forbidden words with constant lengths. In: 2010 International Symposium On Information Theory & Its Applications. IEEE, 2010 pp.72-77. doi:10.1109/ISITA.2010.5649621.
• [64] Droubay X, Justin J, Pirillo G. Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci., 2001. 255(1-2):539-553.
• [65] de Luca A, Glen A, Zamboni LQ. Rich, Sturmian, and trapezoidal words. Theor. Comput. Sci., 2008. 407(1-3):569-573. doi:10.1016/j.tcs.2008.06.009.
• [66] Ayad LAK, Barton C, Pissis SP. A faster and more accurate heuristic for cyclic edit distance computation. Pattern Recognit. Lett., 2017. 88:81-87. doi:10.1016/j.patrec.2017.01.018.
• [67] Glaister I, Shallit J. A Lower Bound Technique for the Size of Nondeterministic Finite Automata. Information Processing Letters, 1996. 59(2):75-77.
• [68] Bernardini G, Chen H, Loukides G, Pisanti N, Pissis SP, Stougie L, Sweering M. String Sanitization Under Edit Distance. In: Gørtz IL, Weimann O (eds.), Proc. CPM 2020, volume 161 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2020 pp. 7:1-7:14. doi:10.48550/arXiv.2007.08179.
• [69] Larsen KG, van Walderveen F. Near-Optimal Range Reporting Structures for Categorical Data. In: Khanna S (ed.), Proc. SODA 2013. SIAM, 2013 pp. 265-276. doi:10.1137/1.9781611973105.20.
• [70] Nekrich Y. Efficient range searching for categorical and plain data. ACM Trans. Database Syst., 2014. 39(1):9:1-9:21. doi:10.1145/2543924.
• [71] Chan TM, Patrascu M. Counting Inversions, Offline Orthogonal Range Counting, and Related Problems. In: Charikar M (ed.), Proc. SODA 2010. SIAM, 2010 pp. 161-173. doi:10.1137/1.9781611973075.15.
• [72] Schieber B. Computing a Minimum-Weight k-Link Path in Graphs with the Concave Monge Property. In: Proc. SODA 1995. ACM/SIAM, 1995 pp. 405-411.
• [73] Aggarwal A, Schieber B, Tokuyama T. Finding a Minimum-Weight k-Link Path Graphs with the Concae Monge Property and Applications. Discret. Comput. Geom., 1994. 12:263-280.
• [74] Bein WW, Larmore LL, Park JK. The d-Edge Shortest-Path Problem for a Monge Graph. Technical Report, 1992. SAND–92-1724C:1-10.
• [75] Allauzen C, Mohri M. Linear-Space Computation of the Edit-Distance between a String and a Finite Automaton. CoRR, 2009. abs/0904.4686. 0904.4686, URL http://arxiv.org/abs/0904.4686.
• [76] Benedikt M, Puppis G, Riveros C. Bounded repairability of word languages. J. Comput. Syst. Sci., 2013. 79(8):1302-1321. doi:10.1016/j.jcss.2013.06.001.
• [77] Benedikt M, Puppis G, Riveros C. Regular Repair of Specifications. In: Proc. LICS 2011. IEEE Computer Society, 2011 pp. 335-344. doi:10.1109/LICS.2011.43.
• [78] Pighizzini G. How Hard Is Computing the Edit Distance? Inf. Comput., 2001. 165(1):1-13. doi:10.1006/inco.2000.2914.
• [79] Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit Distance for Pushdown Automata. In: Proc. ICALP 2015, volume 9135 of Lecture Notes in Computer Science. Springer, 2015 pp. 121-133. doi:10.1007/978-3-662-47666-6 10.
• [80] Wagner RA. Order-n Correction for Regular Languages. Commun. ACM, 1974. 17(5):265-268. doi:10.1145/360980.360995.
• [81] Kosolobov D. Computing runs on a general alphabet. Inf. Process. Lett., 2016. 116(3):241-244. doi:10.1016/j.ipl.2015.11.016
• [82] Hamming RW. Error detecting and error correcting codes. Bell Syst. Tech. J., 1950. 29(2):147-160.
• [83] Kosolobov D. Finding the leftmost critical factorization on unordered alphabet. Theor. Comput. Sci., 2016. 636:56-65.
• [84] Gawrychowski P, Kociumaka T, Rytter W, Walen T. Faster Longest Common Extension Queries in Strings over General Alphabets. In: Proc. CPM 2016,, volume 54 of LIPIcs. 2016 pp. 5:1-5:13. doi:10.48550/arXiv.1602.00447.
• [85] Kosche M, Koß T, Manea F, Siemer S. Absent Subsequences in Words. CoRR, 2021. to appear. doi:10.48550/arXiv.2108.13968.
• [86] Backurs A, Indyk P. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). SIAM J. Comput., 2018. 47(3):1087-1097. doi:10.1137/15M1053128.
• [87] Masek WJ, Paterson M. A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci., 1980. 20(1):18-31.
• [88] Levenshtein VI. Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. -Dokl., 1966. 10(8):707-710.
• [89] Bringmann K, Grandoni F, Saha B, Williams VV. Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. In: Proc. FOCS 2016. 2016 pp. 375-384. doi:10.1109/FOCS.2016.48.
• [90] Jayaram R, Saha B. Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard! In: Proc. ICALP 2017, volume 80 of LIPIcs. 2017 pp. 19:1-19:15. doi:10.4230/LIPIcs.ICALP.2017.19.
• [91] Cheon H, Han Y. Computing the Shortest String and the Edit-Distance for Parsing Expression Languages. In: Proc. DLT 2020, volume 12086 of Lecture Notes in Computer Science. 2020 pp. 43-54. doi:10.1007/978-3-030-48516-0 4.
• [92] Cheon H, Han Y, Ko S, Salomaa K. The Relative Edit-Distance Between Two Input-Driven Languages. In: Proc. DLT 2019, volume 11647 of Lecture Notes in Computer Science. 2019 pp. 127-139. doi:10.1007/978-3-030-24886-4 9.
• [93] Han Y, Ko S, Salomaa K. The Edit-Distance between a Regular Language and a Context-Free Language. Int. J. Found. Comput. Sci., 2013. 24(7):1067-1082. doi:10.1142/S0129054113400315.
• [94] Hirschberg DS. A Linear Space Algorithm for Computing Maximal Common Subsequences. Commun. ACM, 1975. 18(6):341-343.
• [95] Dobkin DP, Lipton RJ. On the Complexity of Computations under Varying Sets of Primitives. J. Comput. Syst. Sci., 1979. 18(1):86-91.
• [96] Gabow HN, Tarjan RE. A Linear-Time Algorithm for a Special Case of Disjoint Set Union. In: Proc. 15th STOC. 1983 pp. 246-251.
• [97] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. ISBN 978-0-262-03384-8. URL http://mitpress.mit.edu/books/introduction-algorithms.
• [98] Imai H, Asano T. Dynamic Segment Intersection Search with Applications. In: Proc. FOCS 1984. 1984 pp. 393-402.
• [99] Ehlers T, Manea F, Mercas R, Nowotka D. k-Abelian pattern matching. J. Discrete Algorithms, 2015. 34:37-48. doi:10.1016/j.jda.2015.05.004. URL https://doi.org/10.1016/j.jda.2015.05.004.
• [100] Willard DE. Log-Logarithmic Worst-Case Range Queries are Possible in Space Theta(N). Inf. Process. Lett., 1983. 17(2):81-84. doi:10.1016/0020-0190(83)90075-3. URL https://doi.org/10.1016/0020-0190(83)90075-3.
• [101] Aggarwal A, Klawe MM, Moran S, Shor PW, Wilber RE. Geometric Applications of a Matrix-Searching Algorithm. Algorithmica, 1987. 2:195-208.
• [102] Babenko MA, Gawrychowski P, Kociumaka T, Starikovskaya TA. Wavelet Trees Meet Suffix Trees. In: Proc. SODA 2015. 2015 pp. 572-591. doi:10.1137/1.9781611973730.39
• [103] JáJâ J, Mortensen CW, Shi Q. Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting. In: Proc. ISAAC 2004, volume 3341 of Lecture Notes in Computer Science. 2004 pp. 558-568. doi:10.1007/978-3-540-30551-4 49.
• [104] Aggarwal A, Klawe MM. Applications of generalized matrix searching to geometric algorithms. Discrete Applied Mathematics, 1990. 27(1-2):3-23.
• [105] Patrascu M. Lower bounds for 2-dimensional range counting. In: Proc. STOC 2007. 2007 pp. 40-46. doi:10.1145/1250790.1250797.
• [106] Elzinga CH, Rahmann S, Wang H. Algorithms for subsequence combinatorics. Theor. Comput. Sci., 2008. 409(3):394-404. doi:10.1016/j.tcs.2008.08.035.
• [107] Holub Š, Saari K. On Highly Palindromic Words. Descrete Applied Mathematics, 2009. 157:953-959. doi:10.1016/j.dam.2008.03.039.
• [108] Dress AW, Erdӧs P. Reconstructing Words from Subwords in Linear Time. Annals of Combinatorics, 2004. 8(4):457-462. doi:10.1007/s00026-004-0232-4.
• [109] Berstel J, Karhumӓki J. Combinatorics on Words - A Tutorial. BEATCS: Bulletin of the European Association for Theoretical Computer Science, 2003. 79.
• [110] Manŭch J. Characterization of a Word by its Subwords. In: Developments in Language Theory. 1999 pp. 210-219.
• [111] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages (3 volumes). Springer, 1997.
• [112] Fazekas SZ, Manea F, Mercas R, Shikishima-Tsuji K. The Pseudopalindromic Completion of Regular Languages. Information and Compution, 2014. 239:222-236. doi:10.1016/j.ic.2014.09.001.
• [113] Kari L, Mahalingam K. Watson-Crick Palindromes in DNA Computing. Natural Computing, 2010. 9(2):297-316. doi:10.1007/s11047-009-9131-2.
• [114] Chen HZQ, Kitaev S, M¨utze T, Sun BY. On universal partial words. Electronic Notes in Discrete Mathematics, 2017. 61:231-237. doi:10.1016/j.endm.2017.06.043.
• [115] Rampersad N, Shallit J, Xu Z. The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages. Fundam. Inf., 2012. 116(1-4):223-236. doi:10.3233/FI-2012-680.
• [116] Krӧtzsch M, Masopust T, Thomazo M. Complexity of universality and related problems for partially ordered NFAs. Inf. Comput., 2017. 255:177-192. doi:10.1016/j.ic.2017.06.004.
• [117] Holzer M, Kutrib M. Descriptional and computational complexity of finite automata - A survey. Inf. Comput., 2011. 209(3):456-470. doi:10.1016/j.ic.2010.11.013.
• [118] Goeckner B, Groothuis C, Hettle C, Kell B, Kirkpatrick P, Kirsch R, Solava RW. Universal partial words over non-binary alphabets. Theor. Comput. Sci, 2018. 713:56-65. doi:10.1016/j.tcs.2017.12.022.
• [119] de Bruijn NG. A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen, 1946. 49:758-764.
• [120] Martin MH. A problem in arrangements. Bull. Amer. Math. Soc., 1934. 40(12):859-864.
• [121] Gawrychowski P, Lange M, Rampersad N, Shallit JO, Szykula M. Existential Length Universality. In: Proc. STACS 2020, volume 154 of LIPIcs. 2020 pp. 16:1-16:14. doi:10.4230/LIPIcs.STACS.2020.16.
• [122] Day JD, Fleischmann P, Manea F, Nowotka D. k-Spectra of Weakly-c-Balanced Words. In: Proc. DLT 2019, volume 11647 of Lecture Notes in Computer Science. 2019 pp. 265-277. doi:10.1007/978-3-030-24886-4 20.
• [123] van Emde Boas P. Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space. Inf. Process. Lett., 1977. 6(3):80-82. doi:10.1016/0020-0190(77)90031-X.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).