Parallel detection of all palindromes in a string. (English) Zbl 0873.68039
Summary: This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. An \(O(\log n)\) time, \(n\)-processor algorithm over general alphabets. In the case of constant size alphabets the algorithm requires only \(n/\log n\) processors, and thus achieves an optimal-speedup. 2. An \(O(\log\log n)\) time, \(n\log n/\log\log n\)-processor algorithm over general alphabets. This is the fastest possible time with the number of processors used. These new results improve on the known parallel palindrome detection algorithms by using smaller auxiliary space and either by making fewer operations or by achieving a faster running time.
MSC:
| 68P10 | Searching and sorting |
Keywords:
palindromesReferences:
| [1] | Apostolico, A.; Breslauer, D.; Galil, Z., Optimal parallel algorithms for periods, palindromes and squares, (Proc. 19th Internat. Colloq. on Automata, Languages, and Programming. Proc. 19th Internat. Colloq. on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 623 (1992), Springer: Springer Berlin), 296-307 · Zbl 1425.68466 |
| [2] | Arlazarov, V. L.; Dinie, E. A.; Kronrod, M. A.; Faradzev, I. A., On economic construction of the transitive closure of a directed graph, Soviet Math. Dokl., 11, 1209-1210 (1970) · Zbl 0214.23601 |
| [3] | Brent, R. P., Evaluation of general arithmetic expressions, J. Assoc. Comput. Mach., 21, 201-206 (1974) · Zbl 0276.68010 |
| [4] | Breslauer, D.; Galil, Z., An optimal \(O( log log n)\) time parallel string matching algorithm, SIAM J. Comput., 19, 1051-1058 (1990) · Zbl 0711.68057 |
| [5] | D. Breslauer and Z. Galil, Finding all periods and initial palindromes of a string in parallel, Algorithmica; D. Breslauer and Z. Galil, Finding all periods and initial palindromes of a string in parallel, Algorithmica · Zbl 0833.68053 |
| [6] | Cook, S. A., Linear time simulation of deterministic two-way pushdown automata, (Information Processing, Vol. 71 (1972), North-Holand: North-Holand Amsterdam), 75-80 · Zbl 0255.68015 |
| [7] | Crochemore, M.; Rytter, W., Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Theoret. Comput. Sci., 88, 59-82 (1991) · Zbl 0737.68037 |
| [8] | Fich, F. E.; Ragde, R. L.; Wigderson, A., Relations between concurrent-write models of parallel computation, (Proc. 3rd ACM Symp. on Principles of Distributed Computing (1981)), 179-189 |
| [9] | Fischer, M. J.; Paterson, M. S., String matching and other products, (Karp, R. M., Complexity of Computation (1974), American Mathematical Society: American Mathematical Society Providence, RI), 113-125 · Zbl 0301.68027 |
| [10] | Galil, Z., Two fast simulations which imply some fast string matching and palindrome-recognition algorithms, Inform. Process. Lett., 4, 85-87 (1976) · Zbl 0328.68047 |
| [11] | Galil, Z., Palindrome recognition in real time by a multitape turing machine, J. Comput. System Sci., 16, 140-157 (1978) · Zbl 0386.03020 |
| [12] | Galil, Z., Optimal parallel algorithms for string matching, Inform. and Control, 67, 144-157 (1985) · Zbl 0588.68022 |
| [13] | Galil, Z.; Seiferas, J., A linear-time on-line recognition algorithm for “Palstar”, J. Assoc. Comput. Mach., 25, 102-111 (1978) · Zbl 0365.68058 |
| [14] | Kedem, Z.; Landau, G. M.; Palem, K., Optimal parallel suffix-prefix matching algorithm and applications, (Proc. 1st ACM Symp. on Parallel Algorithms and Architectures (1989)), 388-398 |
| [15] | Knuth, D. E.; Morris, J. H.; Pratt, V. R., Fast pattern matching in strings, SIAM J. Comput., 6, 322-350 (1977) · Zbl 0372.68005 |
| [16] | Lyndon, R. C.; Schutzenberger, M. P., The equation \(a^m = b^{n\) · Zbl 0106.02204 |
| [17] | Manacher, G., A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string, J. Assoc. Comput. Mach., 22, 346-351 (1975) · Zbl 0305.68027 |
| [18] | English translation by R.H. Silverman (Amer. Math. Soc., Providence, RI, 1976) 25 208.; English translation by R.H. Silverman (Amer. Math. Soc., Providence, RI, 1976) 25 208. · Zbl 0326.02027 |
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.
