Deriving the Aho-Corasick Algorithms: A Case Study into the Synergy ofProgramming Methods

摘要

Imperative programs can be derived using methods like stepwise refinement, butthey do not lend themselves very well to transformational programming. The Bird-Meertens approach offers a powerful transformation calculus for functional programs, but it pays little or no attention to imperative algorithms. The paper shows how the two approaches can be combined by giving a transformational derivation of some efficient and practical imperative programs, viz. the Aho-Corasick string pattern matching algorithms.