String Covering: A Survey

Mhaskar, Neerja; Smyth, W.F.

doi:10.3233/FI-222164

Artykuł - szczegóły

Tytuł artykułu

String Covering: A Survey

Autorzy

Mhaskar Neerja , Smyth W.F.

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

DOI

10.3233/FI-222164

Warianty tytułu

Języki publikacji

Abstrakty

The study of strings is an important combinatorial field that precedes the digital computer. Strings can be very long, trillions of letters, so it is important to find compact representations. Here we first survey various forms of one potential compaction methodology, the cover of a given string x, initially proposed in a simple form in 1990, but increasingly of interest as more sophisticated variants have been discovered. We then consider covering by a seed; that is, a cover of a superstring of x. We conclude with many proposals for research directions that could make significant contributions to string processing in future.

Słowa kluczowe

strings quasiperiodicity covers seeds

Wydawca

IOS Press

Czasopismo

Fundamenta Informaticae

Rocznik

2022

Tom

Vol. 190, nr 1

Strony

17--45

Opis fizyczny

Bibliogr. 120 poz., rys.

Twórcy

autor

Mhaskar Neerja

pophlin@mcmaster.ca

Department of Computing and Software McMaster University 1280 Main Street West, Hamilton, ON L8S 4L8, Canada

autor

Smyth W.F.

smyth@mcmaster.ca

Department of Computing and Software McMaster University 1280 Main Street West, Hamilton, ON L8S 4L8, Canada

Bibliografia

[1] Thue A. ¨Uber unendliche Zeichenreichen. Norske Vid. Selsk. Skr. Mat. Nat. Kl. (Cristiania), 1906. 7:1-22.
[2] Smyth B. Computing Patterns in Strings. Pearson/Addison-Wesley, 2003. ISBN 9780201398397.
[3] Crochemore M, Hancart C, Lecroq T. Algorithms on Strings. Cambridge University Press, 2007. doi:10.1017/CBO9780511546853.
[4] Watson JD, Crick FHC. Molecular structure of nucleic acids. Nature, 1953. 171:737-738. URL https://doi.org/10.1038/171737a0.
[5] Apostolico A, Ehrenfeucht A. Efficient Detection of Quasi-periodicities in Strings. Technical Report 90.5, The Leonadro Fibonacci Institute, Trento, Italy, 1990.
[6] Iliopoulos CS, Moore DW, Park K. Covering a String. In: Proc. 4th CM-SIAM Symp. on Discrete Algorithms (SODA), volume LNCS 684. 1993 pp. 54-62. URL https://doi.org/10.1007/BFb0029796.
[7] Iliopoulos CS, Moore DW, Park K. Covering a String. Algorithmica, 1996. 16(1):288-297. doi: https://doi.org/10.1007/BF01955677.
[8] Kociumaka T, Kubica M, Radoszewski J, Rytter W, Wale´n T. A Linear-Time Algorithm for Seeds Computation. ACM Transactions on Algorithms, 2020. 16(2):27/1-27/23. doi: https://doi.org/10.1145/3386369.
[9] Manber U, Myers G. Suffix Arrays: A New Method for On-Line String Searches. In: Proc. 1st CM-SIAM Symp. on Discrete Algorithms (SODA). 1990 pp. 319-327.
[10] Manber U, Myers G. Suffix Arrays: A New Method for On-Line String Searches. SIAM J. Computing, 1993. 22:935-948. URL https://doi.org/10.1137/0222058.
[11] K¨arkk¨ainen J, Sanders P. Simple linear work suffix array construction. In: Proc. 30th International Colloquium on Automata, Languages, and Programming, volume LNCS 2719. 2003 pp. 943-955. doi:https://doi.org/10.1007/3-540-45061-0 73.
[12] Kӓrkkӓinen J, Sanders P, Burkhardt S. Linear work suffix array construction. J. ACM, 2006. 53(6):918-936. URL https://doi.org/10.1145/1217856.1217858.
[13] Kasai T, Lee G, Arimura H, Arikawa S, Park K. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In: Proc. 12th Annual Symp. Combinatorial Pattern Matching (CPM). 2001 pp. 181-192. doi: https://doi.org/10.1007/3-540-48194-X 17.
[14] Smyth WF. Computing regularities in strings: A survey. European J. Combinatorics, 2013. 34(1):3-14. doi:https://doi.org/10.1016/j.ejc.2012.07.010.
[15] Abouelhoda MI, Kurtz S, Ohlebusch E. Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms, 2004. 2(1):53-86. doi:https://doi.org/10.1016/S1570-8667(03)00065-0.
[16] Weiner P. Linear Pattern Matching Algorithms. In: Proc. 14th Annual Symposium on Switching and Automata Theory (SWAT). 1973 pp. 1-11. doi:10.1109/SWAT.1973.13.
[17] Apostolico A. The myriad Virtues of Subword Trees. In: Combinatorial Algorithms on Words, NATO ISI Series. Springer-Verlag, 1985 pp. 85-96. doi:10.1007/978-3-642-82456-2 6.
[18] Puglisi SJ, Smyth WF, Turpin AH. A taxonomy of suffix array construction algorithms. ACM Computing Surveys, 2007. 39(2). URL https://doi.org/10.1145/1242471.1242472.
[19] Christou M, Crochemore M, Iliopoulos CS, Kubica M, Pissis SP, Radoszewski J, Rytter W, Szreder B, Walen T. Efficient seed computation revisited. Theoret. Comput. Sci., 2013. 483:171-181. doi: https://doi.org/10.1016/j.tcs.2011.12.078. Special Issue Combinatorial Pattern Matching 2011.
[20] Aho AV, Hopcroft JE, Ullman JD. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.
[21] Alatabbi A, Islam ASMS, Rahman MS, Simpson J, Smyth WF. Enhanced Covers of Regular & Indeterminate Strings using Prefix Tables. J. Automata, Languages & Combinatorics, 2016. 21(3):131-147. URL https://doi.org/10.25596/jalc-2016-131.
[22] Bland W, Kucherov G, Smyth WF. Prefix table construction and conversion. In: Proc. 24th Internat. Workshop on Combinatorial Algs. (IWOCA), volume LNCS 8288. 2013 pp. 41-53. doi: https://doi.org/10.1007/978-3-642-45278-9 5.
[23] Smyth WF, Wang S. New perspectives on the prefix array. In: Proc. 15th String Processing & Inform. Retrieval Symp. (SPIRE), volume LNCS 5280. 2008 pp. 133-143. doi: https://doi.org/10.1007/978-3-540-89097-3 14.
[24] Iliopoulos CS, Radoszewski J. Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties. In: Proc. 27th Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 54. 2016 pp. 8.1-8.12. doi:10.4230/LIPIcs.CPM.2016.8.
[25] Mhaskar N, Smyth WF. Simple KMP Pattern-Matching on Indeterminate Strings. In: Proc.Prague Stringology Conference (PSC). 2020 pp. 125-133. URL http://www.stringology.org/event/2020/p11.html.
[26] Dehghani H, Lecroq T, Mhaskar N, Smyth WF. Practical KMP/BM style pattern-matching on indeterminate strings. submitted for publication, 2022.
[27] Knuth DE, Morris JH, Pratt VR. Fast pattern matching in strings. SIAM J. Computing, 1977. 6(2):323-350. doi: https://doi.org/10.1137/0206024.
[28] Boyer RS, Moore JS. A fast string searching algorithm. Communications of the ACM, 1977. 20(10):762-772. doi:https://doi.org/10.1145/359842.359859.
[29] Apostolico A, Ehrenfeucht A. Efficient Detection of Quasiperiodicities in Strings. Theoret. Comput. Sci., 1993. 119(2):247-265. doi: https://doi.org/10.1016/0304-3975(93)90159-Q.
[30] Iliopoulos C, Mouchard L. An O(n log n) Algorithm for Computing all Maximal Quasiperiodicities in Strings. In: Proceeding of the Computing: Australasian Theory Symposium (CATS). 1999 pp. 262-272. URL https://hal.science/hal-00465077.
[31] Brodal GS, Pedersen CNS. Finding Maximal Quasiperiodicities in Strings. In: Proc. 11th Annual Symp. Combinatorial Pattern Matching (CPM), volume LNCS 1848. 2000 pp. 397-411. doi: https://doi.org/10.1007/3-540-45123-4 33.
[32] Apostolico A, Farach M, Iliopoulos CS. Optimal superprimitivity testing for strings. Information Processing Letters, 1991. 39(1):17-20. doi: https://doi.org/10.1016/0020-0190(91)90056-N.
[33] Breslauer D. An On-Line String Super primitivity Test. Informtion Processing Letters, 1992. 44(6):345-347. doi: https://doi.org/10.1016/0020-0190(92)90111-8.
[34] Moore D, Smyth WF. An optimal algorithm to compute all the covers of a string. Informtion Processing Letters, 1994. 50:239-246. doi:https://doi.org/10.1016/0020-0190(94)00045-X.
[35] Moore D, Smyth WF. Correction to: An optimal algorithm to compute all the covers of a string. Informtion Processing Letters, 1995. 54:101-103. doi:https://doi.org/10.1016/0020-0190(94)00235-Q.
[36] Czajka P, Radoszewski J. Experimental Evaluation of Algorithms for Computing Quasiperiods. Theoretical Computer Science, 2021. 854:17-29. doi: https://doi.org/10.1016/j.tcs.2020.11.033.
[37] Iliopoulos CS, Park K. A Work-Time Optimal Algorithm for Computing All String Covers. Theoretical Computer Science, 1996. 164(1&2):299-310. doi: https://doi.org/10.1016/0304-3975(96)00047-3.
[38] Li Y, Smyth WF. Computing the Cover Array in Linear Time. Algorithmica, 2002. 32(1):95-106. doi:https://doi.org/10.1007/s00453-001-0062-2.
[39] Crochemore M, Iliopoulos CS, Pissis SP, Tischler G. Cover array string reconstruction. In: Proc. 21st Annual Symp. Combinatorial Pattern Matching (CPM), volume LNCS 6129. 2010 pp. 251-259. doi: https://doi.org/10.1007/978-3-642-13509-5 23.
[40] Moosa TM, Nazeen S, Rahman MS, Reaz R. Linear Time Inference of Strings from Cover Arrays using a Binary Alphabet. In: Proc. 6th International Workshop on Algorithms & Computation (WALCOM), volume LNCS 7151. 2013 pp. 1-16. doi:https://doi.org/10.1007/978-3-642-28076-4 17.
[41] Moosa TM, Nazeen S, Rahman MS, Reaz R. Inferring Strings From Cover Arrays. Discrete Mathematics, Algorithms and Applications, 2013. 05(02):1360005. doi:10.1142/S1793830913600057.
[42] Gawrychowsk P, Kociumaka T, Radoszewski J, Rytter W, Wale T. Universal Reconstruction of a String. Theoret. Comput. Sci., 2020. 812:174-186. doi:https://doi.org/10.1016/j.tcs.2019.10.027.
[43] Crochemore M, Iliopoulos CS, Radoszewski J, Ryttter W, Straszyński J, Waleń T, Zuba W. Shortest Covers of all Cyclic Shifts of a String. In: Proc. 14th International Workshop on Algorithms & Computation (WALCOM), volume LNCS 12049. 2020 pp. 69-80. doi:https://doi.org/10.1007/978-3-030-39881-1 7.
[44] Crochemore M, Iliopoulos CS, Radoszewski J, Ryttter W, Straszyński J, Waleń T, Zuba W. Shortest Covers of all Cyclic Shifts of a String. Theoret. Comput. Sci., 2021. 866:70-81. doi: https://doi.org/10.1016/j.tcs.2021.03.011.
[45] Crochemore M, Iliopoulos CS, Radoszewski J, Rytter W, Straszy´nski J, Wale´n T, Zuba W. Linear-Time Computation of Shortest Covers of All Rotations of a String. In: Proc. 33rd Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 223. 2022 pp. 22:1-22:15. doi:10.4230/LIPIcs.CPM.2022.22.
[46] Crochemore M, Iliopoulos CS, Radoszewski J, Ryttter W, Straszyński J, Waleń T, Zuba W. Internal Quasiperiod Queries. In: Proc. 27th String Processing & Inform. Retrieval Symp. (SPIRE), volume LNCS 12303. 2020 pp. 60-75. doi: https://doi.org/10.1007/978-3-030-59212-7 5.
[47] Matsuoka Y, Aoki T, Inenaga S, Bannai H, Takeda M. Generalized Pattern Matching and Periodicity under Substring Consistent Equivalence Relations. Theoretical Computer Science, 2016. 656:225-233. doi: https://doi.org/10.1016/j.tcs.2016.02.017.
[48] Fine NJ, Wilf HS. Uniqueness Theorems for Periodic Functions. Proc. American Mathematical Society, 1965. 16(1):109-114. doi:https://doi.org/10.2307/2034009.
[49] Kikuchi N, Hendrian D, Yoshinaka R, Shinohara A. Computing Covers under Substring Consistent Equivalence Relations. In: Proc. 27th String Processing & Inform. Retrieval Symp. (SPIRE), volume LNCS 12303. 2020 pp. 131-146. doi: https://doi.org/10.1007/978-3-030-59212-7 10.
[50] Amir A, Iliopoulos CS, Radoszewski J. Two strings at Hamming distance 1 cannot be both quasiperiodic. Information Processing Letters, 2017. 128:54-57. doi:https://doi.org/10.1016/j.ipl.2017.08.005.
[51] Iliopoulos CS, Smyth WF. On-line algorithms for k-covering. In: Proc. 9th Australasian Workshop on Combinatorial Algs. (AWOCA). 1998 pp. 97-106.
[52] Cole R, Iliopoulos CS, Mohamed M, Smyth WF, Yang L. The complexity of the minimum k-cover problem. J. Automata, Languages & Combinatorics, 2005. 10-5/6:641-653. doi:10.25596/jalc-2005-641.
[53] Iliopoulos CS, Mohamed M, Smyth WF. New complexity results for the k-covers problem. Information Sciences, 2011. 181:2571-2575. doi:https://doi.org/10.1016/j.ins.2011.02.009.
[54] Guo Q, Zhang H, Iliopoulos CS. Computing the Minimum Approximate λ-Cover of a String. In: Proc. 13th String Processing & Inform. Retrieval Symp. (SPIRE), volume LNCS 4209. 2006 pp. 49-60. doi: https://doi.org/10.1007/11880561 5.
[55] Guo Q, Zhang H, Iliopoulos C. Computing the λ-covers of a string. Information Sciences, 2007. 177(19):3957-3967. doi: https://doi.org/10.1016/j.ins.2007.02.020.
[56] Zhang H, Guo Q, Iliopoulos CS. Algorithms for Computing the λ-Regularities in Strings. Fundamenta Informaticae, 2008. 84:33-49.
[57] Iliopoulos CS, Perdikuri K, Zhang H. Computing the regularities in biological weighted sequence. String Algorithmics, NATO Book series, King’s College Publications, 2004. pp. 109-128. [58] Radoszewski J, Straszy´nski J. Efficient Computation of 2-Covers of a String. In: Proc. 28th Annual European Symposium on Algorithms (ESA), volume 173. 2020 pp. 77:1-77:17. doi: 10.4230/LIPIcs.ESA.2020.77.
[59] Kociumaka T, Radoszewski J, Rytter W, Pissis SP, Wale´n T. Fast Algorithm for Partial Covers in Words. Algorithmica, 2015. 73(1):217 - 233. doi:https://doi.org/10.1007/s00453-014-9915-3.
[60] Radoszewski J. Linear Time Construction of Cover Suffix Tree and Applications. In: Proc. 31st Annual European Symposium on Algorithms (ESA), volume 274. 2023 pp. 89:1-89:17. doi:10.4230/LIPIcs.ESA.2023.89.
[61] Flouri T, Iliopoulos CS, Kociumaka T, Pissis SP, Puglisi SJ, Smyth WF, Tyczynski W. Enhanced string covering. Theoretical Computer Science, 2013. 506:102 - 114. doi:10.1016/ j.tcs.2013.08.013.
[62] Mhaskar N, Smyth WF. String Covering with Optimal Covers. Journal of Discrete Algorithms, 2018. 51:26-38. Doi :https://doi.org/10.1016/j.jda.2018.09.003.
[63] Mhaskar N, Smyth WF. Frequency covers for strings. Fundamenta Informaticae, 2018. 163(3):275-289. doi:10.3233/FI-2018-1744.
[64] Koponen H, Mhaskar N, Smyth WF. Improved Practical Algorithms to Compute Maximal Covers. In: (submitted). 2023 .
[65] Golding GB, Koponen H, Mhaskar N, Smyth WF. Computing Maximal Covers for Protein Sequences. Journal of Computational Biology, 2023. 30(2):149-160. doi:10.1089/cmb.2021.0520.
[66] Sim JS, Park K, Kim SR, Lee JS. Finding Approximate Covers of Strings. Journal of KIISE: Computer Systems and Theory, 2002. 29(1):16-21.
[67] Zhang L, Blanchet-Sadri F. Algorithms for Approximate k-Covering of Strings. Int. J. Found. Comput. Sci., 2005. 16(6):1231-1251. URL https://doi.org/10.1142/S0129054105003789.
[68] Sim JS, Iliopoulos CS, Park K, Smyth WF. Approximate period of strings. Theoret. Comput. Sci., 2001. 262:557-568. Doi :https://doi.org/10.1016/S0304-3975(00)00365-0.
[69] Christodoulakis M, Iliopoulos CS, Park K, Sim JS. Implementing Approximate Regularities. Mathematical and Computer Modelling, 2005. 42:855-866. Doi: https://doi.org/10.1016/j.mcm.2005.09.013.
[70] Amir A, Levy A, Lubin R, Porat E. Approximate Cover of Strings. Theoret. Comput. Sci., 2019. 793:59-69. doi: https://doi.org/10.1016/j.tcs.2019.05.020.
[71] Amir A, Levy A, Lewenstein M, Lubin R, Porat B. Can We Recover the Cover? Algorithmica, 2019. 81:2857-2875. doi: https://doi.org/10.1007/s00453-019-00559-8.
[72] Amir A, Levy A, Porat E. Quasi-Periodicity Under Mismatch Errors. In: Proc. 29th Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 105. 2018 pp. 4:1-4:15. doi:10.4230/LIPIcs.CPM.2018.4.
[73] Guth O. On Approximate Enhanced Covers under Hamming Distance. Discrete Appl. Math., 2020. 274:67-80. doi: https://doi.org/10.1016/j.dam.2019.01.015.
[74] Guth O, Melichar B, Balik M. Searching All Approximate Covers and their Distance Using Finite Automata. In: Proc. Inf. Technologies — Appls. and Theory. 2008 pp. 21-26. URL https://ceur-ws.org/Vol-414/.
[75] Guth O. Computing All Approximate Enhanced Covers with the Hamming Distance. Proc. 20th Prague Stringology Conference (PSC), 2016. pp. 146-157. URL http://www.stringology.org/event/2016/index.html.
[76] Kedzierski A, Radoszewski J. k-Approximate Quasiperiodicity under Hamming and Edit Distance. In: Proc. 31st Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 161. 2020 pp. 18:1-18:15. doi:10.4230/LIPIcs.CPM.2020.18.
[77] Kedzierski A, Radoszewski J. k-Approximate Quasiperiodicity under Hamming and Edit Distance. Algorithmica, 2022. pp. 566-589. doi:https://doi.org/10.1007/s00453-021-00842-7.
[78] Iliopoulos CS, Korda M. Optimal parallel superprimitivity testing on square arrays. Parallel Processing Letters, 1996. 6(3):299-308. doi: https://doi.org/10.1142/S0129626496000297.
[79] Crochemore M, Iliopoulos CS, Korda M. Two-dimensional prefix string matching and covering on square matrices. Algorithmica, 1998. 20:353-373. doi:https://doi.org/10.1007/PL00009200.
[80] Aho AV, Corasick MJ. Efficient string matching: an aid to bibliographic search. Communications of the ACM, 1975. 18(6):333-340. doi:10.1145/360825.360855.
[81] Popa A, Tanasescu A. An Output-Sensitive Algorithm for the Minimization of 2-Dimensional String Covers. In: Proc. 15th International Conference on Theory and Applications of Models of Computation (TAMC), volume LNCS 11436. 2019 pp. 536-549. doi:https://doi.org/10.1007/978-3-030-14812-6 33.
[82] Charalampopoulos P, Radoszewski J, Rytter W, Wale´n T, Zuba W. Computing Covers of 2D Strings. In: Proc. 32nd Annual Symp. Combinatorial Pattern Matching (CPM). 2021 pp. 12:1-12:20. doi: 10.4230/LIPIcs.CPM.2021.12.
[83] Radoszewski J, Rytter W, Straszy´nski J, Wale´n T, Zuba W. Rectangular Tile Covers of 2D-Strings. In: Proc. 33rd Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 223. 2022 pp. 23:1-23:14. doi:10.4230/LIPIcs.CPM.2022.23.
[84] Alzamel M, Conte A, Denzumi S, Grossi R, Iliopoulos CS, Kurita K, Wasa K. Finding the Anticover of a String. In: Proc. 31st Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 161. 2020 pp. 2.1-2.11. doi:10.4230/LIPIcs.CPM.2020.2.
[85] Amir A, Boneh I, Kondratovsky E. Approximating the Anticover of a String. In: Proc. 27th String Processing & Inform. Retrieval Symp. (SPIRE), volume LNCS 12303. 2020 pp. 99-114. doi: https://doi.org/10.1007/978-3-030-59212-7 8.
[86] Matsuda S, Inenaga S, Bannai H, Takeda M. Computing Abelian Covers and Abelian Runs. Proc. 18th Prague Stringology Conference (PSC), 2014. pp. 43-51. URL http://www.stringology.org/papers/PSC2014.pdf.
[87] Grossi R, Iliopoulos CS, Jansson J, Lim Z, Sung WK, Zuba W. Finding the Cyclic Covers of a String. In: Proc. 17th International Workshop on Algorithms & Computation (WALCOM), volume LNCS 13973. 2023 pp. 139-150. doi: https://doi.org/10.1007/978-3-031-27051-2 13.
[88] Iliopoulos C, Kociumaka T, Radoszewski J, Rytter W, Wale T, Zuba W. Linear Time Computation of Cyclic Roots and Cyclic Covers of a String. In: Proc. 34th Annual Symp. Combinatorial Pattern Matching (CPM). 2023 .
[89] I T, Sugimoto S, Inenaga S, Bannai H, Takeda M. Computing Palindromic Factorizations and Palindromic Covers On-line. In: Proc. 25th Annual Symp. Combinatorial Pattern Matching (CPM), volume LNCS 8486. 2014 pp. 150-161. doi: https://doi.org/10.1007/978-3-319-07566-2 16.
[90] Radoszewski J, Rytter W, Straszyński J, Waleń T, Zuba W. String Covers of a Tree. In: Proc. 28th String Processing & Inform. Retrieval Symp. (SPIRE), volume LNCS 12944. 2021 pp. 68-82. doi: https://doi.org/10.1007/978-3-030-86692-1 7.
[91] Charalampopoulos P, Pissis SP, Radoszewski J, Rytter W, Waleń T, Zuba W. Subsequence Covers of Words. In: Proc. 29th String Processing & Inform. Retrieval Symp. (SPIRE), volume LNCS 13617. 2022 pp. 3-15. doi: https://doi.org/10.1007/978-3-031-20643-6 1.
[92] Iliopoulos CS, Mohammed M, Mouchard L, Perdikuri KG, Smyth WF, Tsakalidis AK. String Regularities with Don’t Cares. Proc. 7th Prague Stringology Conference (PSC), 2002. pp. 65-74. URL http://www.stringology.org/event/2002/index.html.
[93] Bari MF, Rahman MS, Shahriyar R. Finding all covers of an indeterminate string in O(n) time on average. In: Proc. 13thPrague Stringology Conference (PSC). 2009 pp. 263-271. URL http://www.stringology.org/event/2009/index.html.
[94] Iliopoulos CS, Mohamed M, Mouchard L, Perdikuri K, Smyth WF, Tsakalidis AK. String Regularities with Don’t Cares. Nordic J. Comput., 2003. 10(1):40-51.
[95] Holub J, Smyth WF. Algorithms on indeterminate strings. In: Proc. 14th Australasian Workshop on Combinatorial Algs. (AWOCA). 2003 pp. 36-45.
[96] Antoniou P, Crochemore M, Iliopoulos CS, Jayasekera I, Landau GM. Conservative String Covering of Indeterminate Strings. In: Proc. 12th Prague Stringology Conference (PSC). 2008 pp. 108-115. URL http://www.stringology.org/event/2008/index.html.
[97] Antoniou P, Iliopoulos CS, Jayasekera I, Rytter W. Computing repetitive structures in indeterminate strings. In: Proc. 3rd Int’l Conference on Pattern Recognition in Bioinformatics (PRIB), volume LNCS 5265. 2008 URL https://api.semanticscholar.org/CorpusID:8858579.
[98] Crochemore M, Iliopoulos CS, Kociumaka T, Radoszewski J, Rytter W, Walen T. Covering problems for partial words and for indeterminate strings. Theoret. Comput. Sci., 2017. 698:25-39. doi: https://doi.org/10.1016/j.tcs.2017.05.026.
[99] Zhang H, Guo Q, Iliopoulos CS. Varieties of Regularities in Weighted Sequences. In: Proc. 6th International Conf. on Algorithmic Aspects in Information and Management, volume LNCS 7124. 2010 pp. 271-280. doi: https://doi.org/10.1007/978-3-642-14355-7 28.
[100] Iliopoulos CS, Makris C, Panagis Y, Perdikuri K, Theodoridis E, Tsakalidis A. The Weighted Suffix Tree: An Efficient Data Structure for Handling Molecular Weighted Sequences and its Applications. Fundamenta Informaticae, 2006. 71:259-277.
[101] Barton C, Kociumaka T, Lie C, Pissis SP, Radoszewski J. Indexing Weighted Sequences: Neat and Efficient. Information and Computation, 2019. 270:104462.1-104462.21. doi:10.1016/ j.ic.2019.104462.
[102] Berkman O, Iliopoulos CS, Park K. The Subtree Max Gap Problem with Application to parallel String Covering. Information and Computation, 1995. 123:127-137. doi:10.1006/inco.1995.1162.
[103] Smyth W. Repetitive perhaps, but certainly not boring. Theoretical Computer Science, 2000. 246:343-355. doi: https://doi.org/10.1016/S0304-3975(00)00067-0.
[104] Kociumaka T, Kubica M, Radoszewski J, Rytter W, Wale´n T. A Linear-Time Algorithm for Seeds Computation. In: Proc. 23rd CM-SIAM Symp. on Discrete Algorithms (SODA). 2012 pp. 1095-1112.
[105] Christou M, Crochemore M, Guth O, Iliopoulos CS, Pissis SP. On the left and right seeds of a string. J. Discrete Algorithms, 2012. 17:31-44. doi: https://doi.org/10.1016/j.jda.2012.10.004.
[106] Christou M, Crochemore M, Iliopoulos CS, Kubica M, Pissis SP, Radoszewski J, Rytter W, Szreder B, Walen T. Efficient seeds computation revisited. In: Proc. 22nd Annual Symp. Combinatorial Pattern Matching (CPM), volume LNCS 6661. 2011 pp. 350-363. doi: https://doi.org/10.1007/978-3-642-21458-5 30.
[107] Christou M, Crochemore M, Guth O, Iliopoulos CS, Pissis SP. On the right-seed array of a string. In: Proc. 17th Annual International Computing & Combinatorics Conference (COCOON). 2012 pp. 492-502. doi: https://doi.org/10.1007/978-3-642-22685-4 43.
[108] Crochemore M. An optimal algorithm for computing the repetitions in a word. Informtion Processing Letters, 1981. 12(5):244-250. doi:https://doi.org/10.1016/0020-0190(81)90024-7.
[109] Guo Q, Zhang H, Iliopoulos CS. Computing the λ-Seeds of a String. In: Proc. 2nd International Conf. on Algorithmic Aspects in Information and Management, volume LNCS 4041. 2006 pp. 303-313. doi: 10.1007/11775096 28.
[110] Christodoulakis M, Iliopoulos CS, Park K, Sim JS. Approximate Seeds of Strings. J. Automata, Languages & Combinatorics, 2005. 10(5/6):609-626. doi:10.25596/jalc-2005-609.
[111] Maier D. The Complexity of Some Problems on Subsequences and Supersequences. J. ACM, 1978. 25(2):322-336. doi: https://doi.org/10.1145/322063.322075.
[112] R¨aih¨a Rӓ¨aih¨a K, Ukkonen E. The Shortest Common Supersequence Problem over Binary Alphabet is NP-Complete. Theoret. Comput. Sci., 1981. 16:187-198. doi:10.1016/0304-3975(81)90075-X.
[113] Guth O, Melichar B. Using Finite Automata Approach for Searching Approximate Seeds of Strings. In: Proc. Intelligent Automation and Computer Engineering, volume LNCS 52. 2010 pp. 347-360. doi: 10.1007/978-90-481-3517-2-27.
[114] Guth O, Melichar B. Searching All Seeds of Strings with Hamming Distance using Finite Automata. In: Proc. International Mult iConference of Engineers and Computer Scientists (IMECS), volume 1. 2009 URL https://www.iaeng.org/publication/IMECS2009/.
[115] Guth O, Melichar B. Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance. IAENG International Journal of Computer Science, 2009. 36(2). URL https://www.iaeng.org/IJCS/issues v36/issue 2/.
[116] Guth O. Searching Regularities in Strings using Finite Automata. Ph.D. thesis, Czech Technical University in Prague, Zikova 1903/2, Praha, CZ 160 00, 2014.
[117] Kociumaka T, Pissis SP, Radoszewski J, Rytter W, Walen T. Efficient algorithms for shortest partial seeds in words. Theoret. Comput. Sci., 2018. 710:139-147. doi:https://doi.org/10.1016/j.tcs.2016.11.035.
[118] Gawrychowski P, Radoszewski J, Starikovskaya T. Quasi-Periodicity in Streams. In: Proc. 30th Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 128. 2019 pp. 22:1-22:14. doi: 10.4230/LIPIcs.CPM.2019.22.
[119] Kociumaka T, Radoszewski J, Winiewski B. Subquadratic-Time Algorithms for Abelian Stringology Problems. In: Proc. 6th Mathematical Aspects of Computer and Information Sciences (MACIS), volume LNCS 9582. 2015 doi:https://doi.org/10.1007/978-3-319-32859-1 27.
[120] Radoszewsk J, Rytter W, Straszyski J, Walen T, Zuba W. Hardness of Detecting Abelian and Additive Square Factors in Strings. In: Proc. 29th Annual European Symposium on Algorithms (ESA), volume LIPIcs 2021. 2021 pp. 77:1-77:19. doi:10.4230/LIPIcs.ESA.2021.77

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-21d52360-7d04-4aea-907e-fa41a255c925