Can I read Sequential Algorithms, Deterministic Parallelism, and Intensional Expressiveness on EtoBox?

Sequential Algorithms, Deterministic Parallelism, and Intensional Expressiveness by Stephen Brookes; Denis Dancanet is a scholarly article available to read on EtoBox.

What is Sequential Algorithms, Deterministic Parallelism, and Intensional Expressiveness about?

In the first part of this paper, we study the expressibility of the minimum function, which computes the minimum of two natural numbers represented in unary form (O, S(0), . . . . where S stands for successor). We look at various algorithms computing minimum, which agree when the inputs are fully defined (as they must, since they all compute minimum), but may disagree on undefined or partial inputs.A natural way to define minimum is by the following rewrite system: rnin(x, O) = O rnin(O, x) = O 7nin(S(z), S(y)) = S(min(z, y)) We need to distinguish between the function min (the least function satisfying the rewrite rules above), and an algorithm for rein, which we denote min~. Intuitively, the algorithm based on the above rewrite rules computes its result in time O(min(n, p)) (it takes exactly mtn(n, p) + 1 steps).

Author

Stephen Brookes; Denis Dancanet

Publisher

ACM Press

Published

1995

Language

EN