Recognizing k-rotated segments

This paper explains a calculational design technique for fine-grained parallel programs by means of an example. The example deals with the recognition of K-rotation invariant (or K-rotated) segments which is a generalization of the well known square recognition problem. Two parallel programs are derived. The first one determines for each segment of N successive inputs whether it is K-rotated, the latter determines whether the whole sequence thus far received is K-rotated.