Concurrent term rewriting as a model of computation

A new model of computation, concurrent term rewriting, is proposed as a bridge between a class of easily programmed ultra high level languages and advanced massively concurrent architectures. At the highest level of abstraction, this model views computation as replacing selected subterms by others, at multiple sites concurrently. In this view, concurrent term rewriting provides a standard of correctness, and the choice between using trees or graphs to represent terms is a matter of convenience and efficiency. After introducing the basic concepts and properties of concurrent term rewriting, we discuss some basic implementation issues. A second, more concrete model of computation, called partitioned concurrent term rewriting, takes account of the fact that a (possibly very large) term may be partitioned into fragments that reside on different processors, with each processor concurrently rewriting its own fragment. A number of implementation and optimization issues are also discussed, including overlapping rewrites, rule ordering, compilation, and flow analysis. Concurrent E-strategies are introduced as a flexible control mechanism to optimize performance and facilitate systems programming tasks. All mathematical definitions are gathered in one appendix, while another describes the OBJ language used in examples.