| Автор | Galley, Clive N. |
| Дата выпуска | 1994 |
| dc.description | 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. |
| Формат | application.pdf |
| Издатель | Gordon and Breach Science Publishers |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Тема | Analysis of algorithms |
| Тема | design of algorithms |
| Тема | parallel algorithms |
| Название | On the lower bound for parallel string matching |
| Тип | research-article |
| DOI | 10.1080/00207169408804319 |
| Electronic ISSN | 1029-0265 |
| Print ISSN | 0020-7160 |
| Журнал | International Journal of Computer Mathematics |
| Том | 53 |
| Первая страница | 129 |
| Последняя страница | 133 |
| Аффилиация | Galley, Clive N.; Department of Computer Science, Kings College London, University of London |
| Выпуск | 3-4 |
| Библиографическая ссылка | Breslauer, D. and Galil, Z. 1992. A lower bound for parallel string matching. SI AM Journal on Computing, 21: 856–862. |
| Библиографическая ссылка | Breslauer, D and Galil , Z. 1990. An optimal O(loglogn) parallel string matching algorithm. SI AM Journal on Computing, 19(6): 1051–1058. |
| Библиографическая ссылка | Chen, G. 1992. time algorithm for string matching. Intern. J. Computer Math, 42(6): 185–191. |
| Библиографическая ссылка | Gil, Y., Meyer, F., Heide, Auf Der and Widgerson, A. 1990. Not all keys can be hashed in constant time. Proc. 22nd ACM Symp. on Theory of Computing, 42(6): 244–253. |
| Библиографическая ссылка | Rosser, J. B. and Schoenfield, L. 1962. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6(6): 64–94. |
