The Derivation of a Hierarchy of Algorithms for Pattern Matching on Arrays

This paper derives a hierarchy of algorithms for pattern matching on arrays in the Bird-Meertens calculus for program transformation. In this calculus, both specifications and algorithms are functions, and a few high-level theorems are used as transformation rules. An algorithm is derived from its specification by means of a calculation which typically consists of a sequence of equalities, each an instantiation of a high-level theorem or a definition. Aspects of the Bird-Meertens calculus can be found in [4], [5], [9], [14], [15], and [13]. The laws we use in the derivation are derived from the definition of the data typ