Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Wydawca
Czasopismo
Rocznik
Tom
Strony
33--49
Opis fizyczny
bibliogr. 20 poz., wykr.
Twórcy
autor
autor
autor
- Department of Computer Science and Engineering, Zhejiang University Hangzhou, Zhejiang 310027, China, hzvicky@gmail.com
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS5-0015-0062