Testing String Superprimitivity in Parallel

Abstract

A string w covers 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 0(loglogn) time nlogn/loglogn-processor CRCW-PRAM algorithm that tests if a string is superprimitive. The algorithm is the fastest possible with this number of processors over a general alphabet.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1992
Accession Number
ADA267814

Entities

People

  • Dany Breslauer

Organizations

  • Columbia University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Alphabets
  • Computations
  • Intervals
  • Mathematical Analysis
  • Mathematics

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computational Linguistics
  • Parallel and Distributed Computing.