Computation graphs for actor grammars

摘要

Actor grammars are a model of actor systems based on graph rewriting. Computation graphs model rewriting processes in actor grammars, and hence, computations in actor systems. It is shown that a structured transformation, as introduced in Janssens and Rozenberg (in “Graph Grammars and Their Application to Computer Science,” Lect. Notes in Comput. Sci., Vol. 291, pp. 280–298, Springer-Verlag, Berlin, 1987), may be viewed as a description of the external effect of a computation described by a computation graph. The use of computation graphs in investigating and comparing actor grammars is demonstrated by proving that actor grammars where, in each configuration, each message has a destination, are equivalent (in a well-defined sense) to arbitrary actor grammars.