Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Parallel detection of all palindromes in a string

  • Conference paper
  • First Online:
STACS 94 (STACS 1994)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 775))

Included in the following conference series:

Abstract

This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string:

  1. 1.

    An O(log n) time, n-processor algorithm over general alphabets. In case of constant size alphabets the algorithm requires only n/log n processors, and thus achieves an optimal-speedup.

  2. 2.

    An O(log log n) time, n log n/loglog 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.

Partially supported by NSF Grants CCR-89-00305 and CCR-92-01078, by NATO Grant CRG 900293 and by the National Research Council of Italy.

Partially supported by the European Research Consortium for Informatics and Mathematics postdoctoral fellowship. Part of this work was done while visiting at the Institut National de Recherche en Informatique et en Automatique, Rocquencourt, France.

Partially supported by NSF Grants CCR-90-14605 and CISE Institutional Infrastructure Grant CDA-90-24735.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A. Apostolico, D. Breslauer, and Z. Galil. Optimal Parallel Algorithms for Periods, Palindromes and Squares. In Proc. 19th International Colloquium on Automata, Languages, and Programming, pages 296–307. Springer-Verlag, Berlin, Germany, 1992.

    Google Scholar 

  2. V.L. Arlazarov, E.A. Dinic, M.A. Kronrod, and I.A. Faradzev. On economic construction of the transitive closure of a directed graph. Soviet Math. Dokl., 11:1209–1210, 1970.

    Google Scholar 

  3. R.P. Brent. Evaluation of general arithmetic expressions. J. Assoc. Comput. Mach., 21:201–206, 1974.

    Google Scholar 

  4. D. Breslauer and Z. Galil. An optimal O(loglog n) time parallel string matching algorithm. SIAM J. Comput., 19(6):1051–1058, 1990.

    Google Scholar 

  5. D. Breslauer and Z. Galil. Finding all Periods and Initial Palindromes of a String in Parallel. Technical Report CUCS-017-92, Computer Science Dept., Columbia University, 1992.

    Google Scholar 

  6. S.A. Cook. Linear time simulation of deterministic two-way pushdown automata. In Information Processing 71, pages 75–80. North Holland Publishing Co., Amsterdam, the Netherlands, 1972.

    Google Scholar 

  7. M. Crochemore and W. Rytter. Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays. Theoret. Comput. Sci., 88:59–82, 1991.

    Google Scholar 

  8. F.E. Fich, R.L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation. In Proc. 3rd ACM Symp. on Principles of Distributed Computing, pages 179–189, 1984.

    Google Scholar 

  9. M.J. Fischer and M.S. Paterson. String matching and other products. In R.M. Karp, editor, Complexity of Computation, pages 113–125. American Mathematical Society, Prividence, RI., 1974.

    Google Scholar 

  10. Z. Galil. Two fast simulations which imply some fast string matching and palindrome-recognition algorithms. Inform. Process. Lett., 4(4):85–87, 1976.

    Google Scholar 

  11. Z. Galil. Palindrome Recognition in Real Time by a Multitape Turing Machine. J. Comput. System Sci., 16(2):140–157, 1978.

    Google Scholar 

  12. Z. Galil. Optimal parallel algorithms for string matching. Inform. and Control, 67:144–157, 1985.

    Google Scholar 

  13. Z. Galil and J. Seiferas. A Linear-Time On-Line Recognition Algorithm for “Palstar”. J. Assoc. Comput. Mach., 25(1):102–111, 1978.

    Google Scholar 

  14. Z. Kedem, G.M. Landau, and K. Palem. Optimal parallel suffix-prefix matching algorithm and applications. Manuscript, 1988.

    Google Scholar 

  15. D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6:322–350, 1977.

    Google Scholar 

  16. R.C. Lyndon and M.P. Schutzenberger. The equation a m = b n c p in a free group. Michigan Math. J., 9:289–298, 1962.

    Google Scholar 

  17. G. Manacher. A new Linear-Time “On-Line” Algorithm for Finding the Smallest Initial Palindrome of a String. J. Assoc. Comput. Mach., 22, 1975.

    Google Scholar 

  18. A.O. Slisenko. Recognition of palindromes by multihead Turing machines. In V.P. Orverkov and N.A. Sonin, editors, Problems in the Constructive Trend in Mathematics VI (Proceedings of the Steklov Institute of Mathematics, No. 129), pages 30–202. Academy of Sciences of the USSR, 1973. English Translation by R.H. Silverman, pp. 25–208, Amer. Math. Soc., Providence, RI, 1976.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Purdue University, 47907, West Lafayette, IN

    Alberto Apostolico

  2. Dipartimento di Elettronica e Informatica, Università di Padova, 35131, Padova, Italy

    Alberto Apostolico

  3. Istituto di Elaborazione della Informazione, Consiglio Nazionale delle Ricerche, Via S. Maria 46, 56126, Pisa, Italy

    Dany Breslauer

  4. Computer Science Department, Columbia University, 10027, New York, NY

    Zvi Galil

  5. Computer Science Department, Tel-Aviv University, 69978, Ramat-Aviv, Israel

    Zvi Galil

Authors
  1. Alberto Apostolico
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dany Breslauer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zvi Galil
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Patrice Enjalbert Ernst W. Mayr Klaus W. Wagner

Rights and permissions

Reprints and permissions

Copyright information

© 1994 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Apostolico, A., Breslauer, D., Galil, Z. (1994). Parallel detection of all palindromes in a string. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds) STACS 94. STACS 1994. Lecture Notes in Computer Science, vol 775. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57785-8_166

Download citation

  • DOI: https://doi.org/10.1007/3-540-57785-8_166

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-57785-0

  • Online ISBN: 978-3-540-48332-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation