Fast parallel Lyndon factorization with applications. (English) Zbl 0815.68066
Summary: It is shown that the Lyndon decomposition of a word of \(n\) symbols can be computed by an \(n\)-processor CRCW PRAM in \(O(\log n)\) time. Extensions of the basic algorithm convey, within the same time and processors bounds, efficient parallel solutions to problems such as finding the lexicographically minimum or maximum suffix for all prefixes of the input string, and finding the lexicographically least rotation of all prefixes of the input.
MSC:
| 68Q42 | Grammars and rewriting systems |
Keywords:
Lyndon decompositionReferences:
| [1] | Aho, A. V., J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. · Zbl 0326.68005 |
| [2] | Akl, A. G., and T. G. Toussaint, An Improved Algorithm To Check for Polygon Similarity,Information Processing Letters,7, 127-128 (1978). · Zbl 0374.68061 · doi:10.1016/0020-0190(78)90073-X |
| [3] | Apostolico, A., M. J. Atallah, L. L. Larmore, and H. S. McFaddin, Efficient Parallel Algorithms for String Editing and Related Problems,Proceedings of the 26th Allerton Conference on Communications, Control, and Computing, Monticello, IL, Sept. 1988. Also inSIAM Journal on Computing,19, 968-988 (1990). · Zbl 0711.68055 · doi:10.1137/0219066 |
| [4] | Apostolico, A., and M. Crochemore, Optimal Canonization of All Substrings of a String,Information and Computation,95, 76-95 (1991). · Zbl 0757.68060 · doi:10.1016/0890-5401(91)90016-U |
| [5] | Apostolico, A., and Z. Galil (eds.),Combinatorial Algorithms on Words, NATO ASI Series F, Vol. 12, Springer-Verlag, New York, 1985. · Zbl 0564.00027 |
| [6] | Apostolico, A., C. Iliopoulos, G. Landau, B. Schieber, and U. Vishkin, Parallel Construction of a Suffix Tree, with Applications,Algorithmica,3, 347-365 (1988). · Zbl 0646.68080 · doi:10.1007/BF01762122 |
| [7] | Beame, P., and J. Hastad, Optimal Bounds for Decision Problems on the CRCW PRAM,Journal of the Association for Computing Machinery,36(3), 643-670 (1989). · Zbl 0825.68378 |
| [8] | Berkman, O., D. Breslauer, Z. Galil, B. Schieber, and U. Vishkin, Highly Parallelizable Problems,Proceedings of the 21st ACM Symposium on Theory of Computing, Seattle, WA, May 1989, pp. 309-319. |
| [9] | Chen, K. T., R. H. Fox, and R. C. Lyndon, Free Differential Calculus, IV,Annals of Mathematics,68, 81-95 (1958). · Zbl 0142.22304 · doi:10.2307/1970044 |
| [10] | Crochemore, M., and D. Perrin, Two-Way String-Matching,Journal of the Association for Computing Machinery,38, 651-675 (1991). · Zbl 0808.68063 |
| [11] | Crochemore, M., and W. Rytter, Usefulness of the Karp-Miller-Rosenberg Algorithm in Parallel Computations on Strings and Arrays,Theoretical Computer Science,88, 59-82 (1991). · Zbl 0737.68037 · doi:10.1016/0304-3975(91)90073-B |
| [12] | Duval, J. P., Factorizing Words over an Ordered Alphabet,Journal of Algorithms,4, 363-381 (1983). · Zbl 0532.68061 · doi:10.1016/0196-6774(83)90017-2 |
| [13] | Fich, F. E., R. L. Ragde, and A. Wigderson, Relations Between Concurrent-Write Models of Parallel Computation,SIAM Journal on Computing,17, 606-627 (1988). · Zbl 0652.68065 · doi:10.1137/0217037 |
| [14] | Galil, Z., Optimal Parallel Algorithms for String Matching,Information and Control,67, 144-157 (1985). · Zbl 0588.68022 · doi:10.1016/S0019-9958(85)80031-0 |
| [15] | Lothaire, M.,Combinatorics on Words, Addison-Wesley, Reading, MA, 1982. · Zbl 1001.68093 |
| [16] | Paige, R. R., R. Tarjan, and R. Bonic, A Linear Time Solution to the Single Function Coarsest Partition Problem,Theoretical Computer Science,40, 67-84 (1985). · Zbl 0574.68060 · doi:10.1016/0304-3975(85)90159-8 |
| [17] | Shiloach, Y., Fast Canonization of Circular Strings,Journal of Algorithms,2, 107-121 (1981). · Zbl 0459.68035 · doi:10.1016/0196-6774(81)90013-4 |
| [18] | Siromoney, R., and L. Mathew, A Public Key Cryptosystem Based on Lyndon Words,Information Processing Letters,35(1), 33-36 (1990). · Zbl 0706.68065 · doi:10.1016/0020-0190(90)90170-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
