Author: Lindsay Groves
Source: GZipped PostScript (63kb); Adobe PDF
(290kb)
We show how several language recognition algorithms can be derived from a single abstract algorithm. This is done using a strategy that involves doing the initial development with a generalised specification, and then specialising the specification, and the development to that point, when this is necessary to expedite later steps - in particular, to allow data refinements. This strategy makes it clear which steps depend on which parts of the specification; we believe it also reflects more accurately the way in which many algorithms are actually discovered. This approach also focusses our attention on finding a common abstraction from which several familiar algorithms can be derived, which increases our understanding of the relationships between these algorithms, and suggests directions for deriving other related algorithms.