CALCULATING RECURRENCES USING THE BIRD-MEERTENS FORMALISM
Wentong Cai, David B. Skillicorn · Parallel Processing Letters · 1995
The Bird-Meetens formalism is an approach to software development and computation based on datatype theories. In this paper we build new operators for the theory of lists that compute generalized recurrences and show that they have logarithmic parallel time complexity. As many applications can be cast as forms of recurrences, this allows a large range of parallel algorithms to be derived within the Bird-Meertens formalism. We illustrate by deriving a parallel solution to the maximum segment sum problem.