Algorithms for Computing the [lambda]-regularities in Strings

• Autorzy: Zhang H. , Guo Q. , Iliopoulos C.S.
• Języki publikacji: EN

Abstrakty

EN

We introduce the notion of [lambda]-regularities in strings that consist of [lambda]-covers and [lambda]-seeds, and study three [lambda]-regularities problems- the [lambda]-cover problem, the general [lambda]-cover problem and the [lambda]-seed problem in this paper. [lambda]-regularities can be viewed as generalized string regularities in the sense that a set of [lambda] repetitive strings rather than a single repeated string are considered. We first present a general algorithm for computing all the [lambda]-combinations of a given string, since they serve as candidates for both [lambda]-covers and [lambda]-seeds. The running time of this algorithm is O(n2). Relying on this result, we answer the above mentioned three problems all in O(n2) time.

Słowa kluczowe

EN

lambda-cover problem; general lambda-cover problem; lambda-seed problem; lambda-combinations; equivalence class tree; Reverses Equivalence Class Tree; string regularities; lambda-regularities

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 1
• Strony: 33--49
• Opis fizyczny: bibliogr. 20 poz., wykr.

Twórcy

autor

Zhang H.

autor

Guo Q.

autor

Iliopoulos C.S.

• Department of Computer Science and Engineering, Zhejiang University Hangzhou, Zhejiang 310027, China,

Bibliografia

• [1] Apostolico, A., Farach, M., Iliopoulos, C.S.: Optimal superprimitivity testing for strings, Information Processing Letters, 39, 1991, 17-20.
• [2] Apostolico, A., Preparata, F.P.: Optimal off-line detection of repetitions in a string. Theoretical Computer Science, 22, 1983, 297-315.
• [3] Breslauer, D.: An on-line string superprimitivity test. Information Processing Letters, 44, 1992, 345-347.
• [4] Breslauer, D.: Testing string superprimitivity in parallel. Information Processing Letters, 49, 1994, 235-241.
• [5] Ben-Amram, A.M., Berkman, O., Iliopoulos, C.S., Park, K.: The subtree max gap problem with application to parallel string covering. Proc. of the 5th ACM-SIAM Symp. on Discrete Algorithms, Arlington, Virginia, 1994, 501-510.
• [6] Cole, R., Iliopoulos, C.S., Mohamed, M., Smyth, W.F., Yang, L.: Computing the minimum k-cover of a string. Proc. of the 2003 Prague Stringology Conference (PSC'03), 2003, 51-64.
• [7] Crochemore, M.: An Optimal Algorithm for Computing the Repetitions in a Word. Information Processing Letters, 12(5), 1981, 244-250.
• [8] Guo, Q., Zhang, H., Iliopoulos, C.S.: Computing the _-seeds of a string. Proc. of the Second International Conference on Algorithmic Aspects in Information and Management (AAIM'06), Lecture Notes in Computer Science, volume 4041, Springer Verlag, 2006, 303-313.
• [9] Guo, Q., Zhang, H., Iliopoulos, C.S.: Computing the _-covers of a string. Information Sciences, to appear.
• [10] Gabig, M., Wegrzyn, G.: An introduction to DNA chips: principles, technology, applications and analysis, Acta Biochimica Polonica, 48(3), 2001, 615-622.
• [11] Iliopoulos, C.S., Moore, D.W.G., Park, K.: Covering a string. Algorithmica, 16, 1996, 288-297.
• [12] Iliopoulos, C.S., Mohamed, M., Smyth, W.F.: New complexity results for the k-covers problem, Proc. 15th Australasian Workshop on Combinatorial Algorithms, 2004, 141-147.
• [13] Iliopoulos, C.S., Park, K.: An optimal O(log log n) time algorithm for parellel superprimitivity testing. J. of the Korean Information Science Society, 21(8), 1994, 1400-1404.
• [14] Iliopoulos, C.S., Park, K.: An O(log log n) PRAM algorithm for computing all the seeds of a string. Theoretical Computer Science, 2(164), 1996, 299-310.
• [15] Iliopoulos, C.S., Pedikuri, K., Zhang, H: Computing the regularities in biological weighted sequence. in: String Algorithmics, NATO Book series (C. S. Iliopoulos, Thierry Lecroq, eds.), King's College Publications, 2004, 109-128.
• [16] Iliopoulos, C.S., Smyth, W.F.: An on-line algorithm of computing a minimum set of k-covers of a string. Proc. of the Ninth Australian Workshop on Combinatorial Algorithms (AWOCA), 1998, 97-106.
• [17] Li, Y., Smyth, W.F.: Computing the cover array in linear time. Algorithmica, 32(1), 2002, 95-106.
• [18] Moore, D.W.G., Smyth,W.F.: A correction to "Computing the covers of a string in linear time". Information Processing Letters, 54, 1995, 101-103.
• [19] Skiena, S.S., Sundaram, G.: Reconstructing strings from substrings, Lecture notes in Computer Science, volume 709, 1993, 565-594.
• [20] Zhang,H., Guo, Q. Iliopoulos, C.S.: Computing the _-covers of a string. Proceedings of the 17th Australasian Workshop on Combinatorial Algorithms (AWOCA 2006), 2006.