Equivalence of computations in actor grammars (Q685461)

Actor grammars were introduced by \textit{D. Janssens} and \textit{G. Rozenberg} [Lect. Notes Comput. Sci. 291, 280-298 (1987; Zbl 0643.68029)] as a formal model for actor systems of \textit{C. Hewitt} [Inf. Process. 77, Proc. IFIP Congr., Toronto 1977, 987-992 (1977; Zbl 0363.68077)]. The paper approaches two main topics. First, it is shown that the order in which primitive rewritings occur is irrelevant for rewriting processes of actor grammars. The notion of a computation graph is introduced and used in this aim. The second issue considered is related to the problem of designing actor grammars in a modular way. To this end the notion of structured transformation introduced by \textit{D. Janssens} and \textit{G. Rozenberg} [Math. Syst. Theory 22, 75-107 (1989; Zbl 0677.68082)] is used and shown to correspond to a notion of equivalence of computations (external equivalence): two computations are externally equivalent if and only if the structured transformations determined by them are equal.