Evolving Algebras

Yuri Gurevich , University of Michigan

The main goal of the evolving algebra method is to provide succint and executable formal specifications for algorithms. Here the term algorithm is taken in a broad sense including programming languages, architectures, distibuted and real-time protocols, etc... Such specifications may be used for designing algorithms ; for testing, verifying and proving various properties of algorithms ; for documenting, maintaining, understanding and teaching algorithms. The EA project started as an attempt to improve on Turing's thesis. Computation models and specification methods seem to be world apart. The EA project may be seen as an attempt to bridge the gap. The EA thesis says, rougly speaking, that every algorithm can be viewed as an evolving algebra. The EA computation model has been used to prove a linear-time hierarchy theorem, but for the most part evolving algebra are used for specification and related purposes. In the talk, we plan to motivate and explain basic evolving algebras, argue for the EA thesis, state the linear-time hierarchy theorem and illustrate the uses of evolving algebras as specification tool.