On the lower bound for parallel string matching
Galley, Clive N.; Galley, Clive N.; Department of Computer Science, Kings College London, University of London
Журнал:
International Journal of Computer Mathematics
Дата:
1994
Аннотация:
This paper shows a string length improvement to the O(loglogm) lower bound on the number of rounds needed to find occurrences of a pattern half the length of a text string. m in Breslauer/GahTs result [BG], the previous lower bound was 5.075-10<sup>35</sup> Here it is shown that there is a lower bound for the same constant for all m ≥2<sup>48</sup>. For increasing m the constant can be improved. Given the lower bound for hashing in [GMW] the algorithm in [C] cannot be implemented in 0(1) time and for m ≥2<sup>48</sup> the algorithm cannot be implemented in 0(log* m) time.
143.4Кб