FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:   || 2 |

«Parallel Detection of all Palindromes in a String Alberto Apostolico Dany Breslauery Zvi Galilz Abstract This paper presents two e cient ...»

-- [ Page 1 ] --

Parallel Detection of all Palindromes in a


Alberto Apostolico Dany Breslauery Zvi Galilz


This paper presents two e cient concurrent-read concurrent-write parallel algorithms that nd all palindromes in a given string:

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. 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.

1 Introduction Palindromes are symmetric strings that read the same forward and backward.

Palindromes have been studied for centuries as word puzzles and more recently have found several important uses in formal languages and computability theory.

Formally, a non-empty string w is a palindrome if w = wR, where wR denotes the string w reversed. It is convenient to distinguish between even length Computer Science Department, Purdue University, West Lafayette, IN 47907, and Dipartimento di Elettronica e Informatica, Universita di Padova, 35131 Padova, Italy. 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.

y Istituto di Elaborazione della Informazione, Consiglio Nazionale delle Ricerche, Via S. Maria 46, 56126 Pisa, 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.

z Computer Science Department, Columbia University, New York, NY 10027, and Computer Science Department, Tel-Aviv University, Ramat-Aviv 69978, Israel. Partially supported by NSF Grants CCR-90-14605 and CISE Institutional Infrastructure Grant CDA-90-24735.

palindromes that are strings of the form vvR and odd length palindromes that are strings of the form vavR, where a is a single alphabet symbol.

Given a string S 1::n], we say that there is an even palindrome of radius R centered at position k of S 1::n], if S k ? i] = S k + i ? 1] for i = 1; ; R. We ^ say that there is an odd palindrome of radius R centered on position k of S 1::n], ^ ^ if S k ? i] = S k + i] for i = 1; ; R. The radius R (or R) is maximal if there 1 R + 1 centered at the same position. In this paper we is no palindrome of radius ^ are interested in computing the maximal radii R k] and R k] of the even and the odd palindromes which are centered at all positions k of S 1::n].

Manacher 17] discovered an elegant linear-time on-line sequential algorithm that nds all initial palindromes in a string. Galil 11] and Slisenko 18] presented real-time initial palindrome recognition algorithms for multi-tape Turing machines.

It is interesting to note that the existence of e cient algorithms that nd initial palindromes in a string was also implied by theoretical results on fast simulation 6, 10]. Knuth, Morris and Pratt 15] gave another linear-time algorithm that nds all initial palindromes in a string.

A closer look at Manacher's algorithm shows that it not only nds the initial palindromes, but it also computes the maximal radii of palindromes centered at all positions of the input string. Thus Manacher's algorithm solves the problem considered in this paper in linear time.

A parallel algorithm is said to be optimal, or to achieve an optimal-speedup, if its time-processor product, which is the total number of operation performed, is equal to the running time of the fastest sequential algorithm. Note that there exists a trivial constant-time CRCW-PRAM algorithm that nds all palindromes in a string using O(n2) processors. However, the large number of processors leaves much to be desired.

Fischer and Paterson 9] noticed that any string matching algorithm that nds all overhanging occurrences of a string in another can also nd all initial palindromes. This observation has been used by Apostolico, Breslauer and Galil 1] to construct an optimal O(log log n) time parallel algorithm that nds all initial palindromes in strings over general alphabets, improving an O(log n) time nonoptimal algorithm of Galil 12]. Breslauer and Galil 5] show that any parallel algorithm that nds initial palindromes in strings over general alphabets requires (dn=pe + log logd1+p=ne 2p) time using p processors. Thus, the fastest possible optimal parallel algorithm that nds initial palindromes must take (log log n) time and this is the time required even with n log n processors.

Crochemore and Rytter 7] discuss a general framework for solving string problems in parallel. (Similar results have been discovered by Kedem, Landau and Palem 14].) Most problems they consider, including the problem of detecting For the convenience of our notation, we sometimes refer to indices in S 1::n] that are out of the de ned range. It is agreed that all unde ned symbols are distinct and di erent from the symbols in S 1::n].

all palindromes in a string, have O(log n) time, n-processor CRCW-PRAM algorithms. However, their method uses O(n1+ ) space and requires that the input symbols are drawn from an ordered alphabet, an unnecessary restriction in the palindrome detection problem.

This paper presents two new CRCW-PRAM algorithms for detecting all palindromes in a string. Both algorithms have the same time-processor product as the Crochemore-Rytter algorithm, use linear space and work under the general alphabet assumption, where the only access they have to the input symbols is by pairwise comparisons that determine if two symbols are equal.

1. The rst algorithm takes O(log n) time using n processors. If the alphabet size is bounded by a constant, then the number of processors can be reduced to n= log n, making the algorithm optimal.

2. The second algorithm takes O(log log n) time using n log n= log log n processors. This algorithm is the fastest possible with the number of processors used since it takes at least this time to nd the initial palindromes.

The paper is organized as follows. Section 2 overviews some parallel algorithms and tools that are used in the new algorithms. Section 3 gives important properties of periods and palindromes. Sections 4 and 5 describe the new algorithms.

Concluding remarks and open problems are listed in Section 6.

2 The CRCW-PRAM Model The algorithms described in this paper are for the concurrent-read concurrentwrite parallel random access machine model. We use the weakest version of this model called the common CRCW-PRAM. In this model many processors have access to a shared memory. Concurrent read and write operations are allowed at all memory locations. If several processors attempt to write simultaneously to the same memory location, it is assumed that they always write the same value.

Our palindrome detection algorithms use an algorithm of Fich, Ragde and Wigderson 8] to compute the minima of n integers from the range 1; ; n, in constant time using an n-processor CRCW-PRAM. The second algorithm uses Breslauer and Galil's 4] parallel string matching algorithm that takes O(log log n) time using an n= log log n-processor CRCW-PRAM.

One of the major issues in the design of PRAM algorithms is the assignment of processors to their tasks. In this paper, the assignment can be done using standard techniques and the following general theorem.

Theorem 2.1 (Brent 3]) Any synchronous parallel algorithm of time t that consists of a total of x elementary operations can be implemented on p processors in dx=pe + t time.

3 Periods and Palindromes Periods are regularities of strings that are exploited in many e cient string algorithms.

De nition 3.1 A string S has a period u if S is a pre x of uk for some large enough k. The shortest period of a string S is called the period of S. Alternatively, a string S 1::m] has a period of length if S i] = S i + ], for i = 1; ; m ?.

Lemma 3.2 (Lyndon and Schutzenberger 16]) If a string of length m has two periods of lengths p and q and p + q m, then it also has a period of length gcd(p; q).

Throughout the paper, we discuss only the detection of even palindromes. If interested also in the odd palindromes, one can convert the input string S 1::n] ^ into a string S 1::2n] that is obtained by doubling each symbol of the original ^ string. It is not di cult to verify that the string S 1::2n] has even palindromes that correspond to each odd and even palindrome of S 1::n]. Thus, the palindrome ^ detection algorithms can be presented with the string S 1::2n] as their input, while their output is considered in the context of the original string S 1::n]. Note that ^ an odd palindrome in S 1::2n] consists of equal symbols.

The palindrome detection algorithms use the following lemmas that allow them to handle e ciently long palindromes that are centered close to each other. The lemmas concern only even palindromes, but there exist similar versions for odd palindromes.

Lemma 3.3 Assume that the string S 1::n] contains two even palindromes whose radii are at least r centered at positions k and l, such that k l and l ? k r.

Then the substring S k ? r::l + r ? 1] is periodic with period length 2(l ? k).

Proof: If 1 i r, then S k ? i] = S k + i ? 1] = S l ? (l ? k) + i ? 1] = S l + (l ? k) ? i] = S k + 2(l ? k) ? i] and S l + i ? 1] = S l ? i] = S k + (l ? k) ? i] = S k ? (l ? k) + i ? 1] = S l ? 2(l ? k) + i ? 1];

establishing that S k ? r::l + r ? 1] is periodic with period length 2(l ? k). 2

–  –  –

4 An O(log n) time algorithm Theorem 4.1 There exists an algorithm that computes the radii of all even palindromes in a string S 1::n] in O(log n) time using n processors and linear space.

Proof: The algorithm consists of blog nc ? 1 steps. In step number, 0 blog nc ? 2, the input string S 1::n] is partitioned into consecutive blocks of length 2. (Only palindrome centers are partitioned. The palindromes themselves may overlap.) The algorithm proceeds simultaneously in all bn=2 c blocks. It takes constant time and makes O(2 ) operations in each block. Therefore, each step takes constant time using n processors.

The description below concentrates on a single block. The ideal situation is when the radii of all palindromes that are centered in the block are determined by the end of the step. However, this will not always be the case. The algorithm

maintains the following invariant at the completion of step number :

The palindromes whose radii are determined are exactly those whose radii are smaller than 2 +2.

The main observation is that at the beginning of step number, the position of all undetermined radii in the block form an arithmetic progression. Let c1 c2 cl be the positions of palindromes whose radii are not determined. We show that if l 3, then ci+1 ? ci = ci ? ci?1 for i = 2; ; l ? 1. By the invariant and Lemma 3.3, S ci?1 ? 2 +1 ::ci + 2 +1 ] is periodic with period length 2(ci ? ci?1) and S ci ? 2 +1 ::ci+1 + 2 +1] is periodic with period length 2(ci+1 ? ci). Therefore, by Lemma 3.2, S ci ? 2 +1::ci + 2 +1 ] is periodic with period length 2c, where c = gcd(ci ? ci?1; ci+1 ? ci). But by Lemma 3.4, if ci ? ci?1 c, then the radius of the palindrome centered at position ci ?c is larger than the radius of the palindrome centered at position ci?1 or the palindrome centered at position ci, violating the invariant. Therefore, ci ?ci?1 = c and similarly also ci+1 ?ci = c, establishing that the sequence of undetermined radii fcig forms an arithmetic progression.

Note that an arithmetic progression can be represented by three integers: the start, the di erence and the sequence length. If the undetermined radii in the two 2 ?1-blocks that compose the current 2 -block are represented this way, then the two representations are merged using constant number of operations. This permits an e cient access to all palindromes whose radii are undetermined.

We show next how to maintain the invariant at the end of each step. The computation takes constant time and O(2 ) operations using symbol comparisons and the integer minima algorithm.

1. If the block contains a single undetermined radius, then the algorithm checks if the radius is at least 2 +2 or nds the radius exactly if it is shorter.

2. If the block contains a non-trivial arithmetic progression of undetermined radii fcig, i = 1::l, with di erence c, then let S L:: R] be the maximal substring that contains S c1 ?c::cl +c?1] and is periodic with period length 2c. By Lemma 3.4, the radius of the palindrome centered at position ci is exactly min(ci ? L; R ?ci +1) except for at most one of the ci's that satis es ci ? L = R ? ci + 1.

The algorithm checks if S c1 ? 2 +2::cl + 2 +2 ? 1] is periodic with period length 2c. If this substring is not periodic, then the algorithm has found at least one of L and R and it can determine all radii which are smaller than 2 +2 by Lemma 3.4. If the algorithm found both L and R and there is a palindrome with undetermined radius centered at position ( L + R + 1)=2, then the algorithm checks if the radius of this palindrome is at least 2 +2 or nds the radius exactly if it is shorter.

Sometime the algorithm nds radii of longer palindromes but we prefer to leave these radii undetermined to maintain the invariant.

In the beginning of step number 0 there is a single undetermined radius in each block and the invariant is satis ed at the end of the step. At the end of step number blog nc ? 2 all radii have been determined. 2 If the size of the alphabet is bounded by some constant, then the O(log n) time algorithm described above can be implemented using only n= log n processors, similarly to Galil's 12] string matching algorithm. This is achieved using the \four Russians trick" 2] of packing log n symbols into one number, in order to facilitate comparisons of up to log n symbols in a single operation. Note, that over general alphabet the algorithm described above is obsolete since the algorithm given in the next section is more e cient.

Pages:   || 2 |

Similar works:

«JBC Papers in Press. Published on September 5, 2001 as Manuscript M107625200 Correlation between uncoupled ATP hydrolysis and heat production by the sarcoplasmic reticulum Ca2+-ATPase Coupling effect of fluoride. Marcelo Reis, Mariana Farage, Angela Cristina L. de Souza and Leopoldo de Meis. From the Departamento de Bioquímica Médica, Instituto de Ciências Biomédicas, Downloaded from http://www.jbc.org/ by guest on December 16, 2016 Centro de Ciências da Saúde, Universidade Federal do Rio...»

«LALEHAM GAP SCHOOL GOVERNING BODY FULL GOVERNING BODY MEETING 2015-16 Minutes of the Meeting of the Full Governing Body held at 1800 hours on Wednesday, 23 March 2016 in the Meeting Room at Laleham Gap School Present: Mr Neil Birch, Miss Lucy Comiskey, Mr Nicholas Holbrook-Sutcliffe (Chairman), Mr Ian Murton (Vice-Chair), Mrs Lesley Price, Mrs Katie Reeves (Interim Headteacher), Mrs Helen Rogers, Dr Roly Speller In Attendance: Mrs Val Woodin (Clerk), Ms Sue Scobie (Assistant Headteacher and...»

«Wilson Bull., 105(3), 1993, pp. 497-503 TROPHIC NICHE OF NEARCTIC SHORT-EARED OWLS DENVER W. HOLT’ AssTticr.-The trophic niche of Short-eared Owls (Asiojlammeus) was analyzed using nine Nearctic studies reporting 500 prey items each. Of 20,416 prey items, 4136 were from the breeding and 16,280 from the non-breeding seasons. The owls preyed upon at least 62 species from four classes of animals. Mammals constituted 95% of prey from all but two sites. Food-niche breadth ranged from 1.23 to 5.20...»

«ONTHAALBROCHURE Medische Beeldvorming Campus Aalst, Ninove OLV Ziekenhuis Campus Aalst Moorselbaan 164 9300 Aalst T. 053 72 41 11 F. 053 72 45 86 Campus Asse Bloklaan 5 1730 Asse T. 02 300 61 11 F. 02 300 63 00 Campus Ninove Biezenstraat 2 9400 Ninove T. 054 31 21 11 F. 054 31 21 21 Inhoud Voorwoord WELKOM DOELSTELLINGEN VOORSTELLING VAN DE DIENST MEDISCHE BEELDVORMING KENNISMAKING EN SITUERING Campus aalst Campus Ninove VOORSTELLING VAN DE VERSCHILLENDE ONDERDELEN VAN DE MEDISCHE BEELDVORMING....»

«October 26, 2014 9:30 am Relevant. Relating to What Matters Lay Lector Kathy Ury Acolyte Emily Letchworth Greeter Karen Kaul Ushers Don & Kari Adams Offering Stewards Connie Gabel, Barb Harris Nursery Care Sandi Wilson Sound System Mary Wilson & Isaac Grimm Coffee Hour Hosts John & Marilyn Blaser CHURCH STAFF Betsy Happel, Pastor (betsy@kirkwooducc.org) Kirkwood United Church of Christ Julie Kies, Student Minister (jjkies@hotmail.com) 1603 Dougherty Ferry Road Donna Bay, Administrative...»

«UNITED STATES DISTRICT COURT FOR THE DISTRICT OF RHODE ISLAND UNITED STATES OF AMERICA : : v. : CR No. 12-154S :JUSTIN LEE WORLEY : MEMORANDUM AND ORDER Before the Court for determination is the government’s Motion for Issuance of Subpoenas Duces Tecum (ECF No. 12) to procure records pertaining to the college education and military service of Defendant Justin Lee Worley, records that the government contends are relevant to sentencing in this matter. The Motion is grounded on Rule 17(c) of the...»

«ANNUAL REPORT 2008 Appendices Geological Survey of Ireland Department of Communications, Energy and Natural Resources Earth Science for Society Roinn Cumarsáide, Fuinnimh agus Acmhainní Nádúrtha GEOLOGICAL SURVEY OF IRELAND (GSI) ANNUAL REPORT 2008 APPENDICES This information supplements that in the GSI Annual Report for 2008, available through www.gsi.ie. Hard copies of the highlights of this report can be obtained from the GSI Customer Centre. Additional information on the work of GSI is...»

«July 29, 2016 Earnings Presentation Q&A for Q1, the Fiscal Year Ending March 31, 2017 Date/Time: July 29, 2016 18:30-19:30 JST Location: NEC Headquarters, Tokyo Presenters: Isamu Kawashima, Executive Vice President and CFO Questioner A Q. Please describe the current state of IT investment sentiment in Japan. A. In Q1, the order trend for IT investment in Japan decreased 6% year on year. This reflected the rebound from strong order growth of 16% in the previous fiscal year, due to growth of...»

«Vietnam 1965, 50 Years On. Colin Geraghty, Service Number O314232, RAAF Caribou Pilot.1. Introduction: 50 Years on, a few recollections of my time as an RAAF Caribou Pilot in the South Vietnam War, during 1965. Some of these situations caused me concern, but were not overwhelming and like everyone else I carried on with my job no matter what happened. Early in the Australian participation in the war our unit, RAAF Transport Flight Vietnam (RTFV), along with a small number of experienced Army...»

«OLIVER! Directors Notes Hi and welcome to the start of the Wakefield Country Players production of the musical Oliver! Written by Lionel Bart and based upon the novel Oliver Twist by Charles Dickens, the musical premiered in London’s West End in 1960. After enjoying a long run on the West End, it opened in New York in 1963 where it won a Tony award for Best Original Score. Quick Synopsis “Oliver!” is a musical classic. It Brings the Charles Dickens novel alive, as we follow orphaned,...»

«Guidelines for Use of Mini-Horizontal Directional Drilling for Placement of High Density Polyethylene Pipe TR-46 Prepared by: Dr. Larry Slavin Member of the HDPE Municipal Advisory Board Outside Plant Consulting Services, Inc. (OPCS) 15 Lenape Avenue, Rockaway, NJ 07866-1019 for The Plastics Pipe Institute 105 Decker Court, Suite 825, Irving, TX 75062 P: 469-499-1044 F: 469-499-1063 www.plasticpipe.org © Copyright, The Plastics Pipe Institute, Inc. 2009 FOREWORD Guidelines for Use of...»

«Table of Contents Chapter 1 Introduction 1.1 Requirements and scope 1.2 Overview Chapter 2 LHCb Software 2.1 Introduction 2.2 Gaudi Architecture & Framework 2.2.1. Generic component model with well defined interfaces 2.2.2. Separation between data and algorithms 2.2.3. Transient and persistent data 2.2.4. Transient data stores 2.2.5. Algorithms 2.2.6. Tools 2.2.7. Services 2.2.8. Core Services 2.3 The LHCb Event Model 2.3.1. Objects in the Transient Event Store 2.3.2. Relationship between...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.