PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Breslauer D. Testing string superprimitivity in parallel. In: Information Processing Letters, vol. 49 (5) pp. 235 - 241. Elsevier, 1994.
 
 
Abstract
(English)
A string w couers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself, and quasiperiodic if it is covered by some shorter string. This paper presents an optimal Ο(α(|z|) log log |z|) time CRCW-PRAM algorithm that tests if a string z is superprimitive, where α(|z|) is the inverse of Ackermann function. An alternative implementation takes Ο(log log |z|) time using (|z|log|z|)/log log|z| processors, and is the fastest possible with this number of processors over a general alphabet.
Subject Parallel algorithms
String matching
Periods
Quasiperiods
Superprimitivity
F.2.1 Numerical Algorithms and Problems


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional