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 <>
Submitted on : Friday, May 19, 2006 - 6:48:55 PM
Last modification on : Thursday, February 11, 2021 - 2:50:06 PM
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

201

Files downloads

181