HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Testing string superprimitivity in parallel

Abstract : A string w convers 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 [??] time CRCW-PRAM algorithm that tests if a string z is superprimitive, where [??] is the inverse of the Ackermann function. An alternative implementation takes [??] processors, and is the fastedt possible with this number of processors over a general alphabet.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00070009
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 6:48:55 PM
Last modification on : Friday, February 4, 2022 - 3:15:13 AM
Long-term archiving on: : Tuesday, February 22, 2011 - 11:02:49 AM

Identifiers

  • HAL Id : inria-00070009, version 1

Collections

Citation

Dany Breslauer. Testing string superprimitivity in parallel. [Research Report] RT-0160, INRIA. 1993, pp.8. ⟨inria-00070009⟩

Share

Metrics

Record views

84

Files downloads

142