Physical parallel devices are not much faster than sequential ones |
| |
Authors: | Amir Schorr |
| |
Affiliation: | National Semiconductor Ltd, Herzlia B 46104, Israel, and School of Mathematical Sciences, Tel-Aviv University, Ramat-Aviv, Tel-Aviv 69978, Israel |
| |
Abstract: | It is proven that any (uniform) family of physical parallel devices, recognizing a language C? with time-complixity TP(n), can be simulated by a (uniform) family of sequential devices with time-complexity (d is a constant, depending on the technology, but not greater than 13). |
| |
Keywords: | Parallel processing theory of computation |
本文献已被 ScienceDirect 等数据库收录! |
|