Testing string superprimitivity in parallel
Résumé
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.