On limits on the computational power of data-accumulating algorithms

✍ Scribed by Stefan D Bruda; Selim G Akl

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 102 KB
• Volume: 86
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(02)00499-4

✦ Synopsis

In the data-accumulating paradigm, inputs arrive continuously in real time, and the computation terminates when all the already received data are processed before another datum arrives. Previous research states that a constant upper bound on the running time of a successful algorithm within this paradigm exists only for particular forms of the data arrival law. This contradicts our recent conjecture that those problems that are solvable in real time are included in the class of logarithmic space-bounded computations. However, we prove that such an upper bound does exist in fact in both the parallel and sequential cases and for any polynomial arrival law, thus strengthening the mentioned conjecture. Then, we analyze an example of a noncontinuous data arrival law. We find similar properties for the sorting algorithm under such a law, namely the existence of an upper bound on the running time, suggesting that such properties do not depend on the form of the arrival law.