Title :
Cost-optimal parallel algorithms for finitely inductive sequences
Author :
Das, Sajal K. ; Fisher, Paul S. ; Zhang, Hua
Author_Institution :
Dept. of Comput. Sci., North Texas Univ., Denton, TX, USA
Abstract :
Finitely inductive (FI) sequences are a class of sequences, finite or infinite, which are amenable to a certain mathematical representation which has direct significance to pattern recognition and string matching. The authors propose cost-optimal parallel algorithms for FI sequence processing. These algorithms include parallel factoring and following by bucket packing and by hashing on an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) model. Each of the algorithms achieves cost-optimal speedup under certain conditions as detailed
Keywords :
computational complexity; file organisation; parallel algorithms; EREW; PRAM; bucket packing; cost-optimal parallel algorithms; finitely inductive sequences; hashing; mathematical representation; parallel factoring; parallel random access machine; pattern recognition; string matching; Computer science; Distributed computing; Impedance matching; Motion detection; Multiple signal classification; Parallel algorithms; Pattern matching; Pattern recognition; Phase change random access memory; Signal detection;
Conference_Titel :
System Sciences, 1993, Proceeding of the Twenty-Sixth Hawaii International Conference on
Conference_Location :
Wailea, HI
Print_ISBN :
0-8186-3230-5
DOI :
10.1109/HICSS.1993.284101
