MONSTR: term graph rewriting for parallel machines
Richard Banach · 1993
DACTL We present here a rather abstract and slightly simplified version of the language DACTL [GKSS88, GHK + 88]. The abstraction takes us away from the tedium of concrete syntax and enables us to concentrate on the semantic issues. We assume we are given an alphabet S = fS; T : : :g of node symbols. We write SeqN for the set of sets of naturals of the form f1 : : : ng, where f1 : : : 0g = ;. Definition 18.2.1 A(n abstract DACTL) term graph (or just graph) G, is a quintuple (N; oe; ff; ¯; ) where (1) N is a set of nodes, (2) oe is a map N ! S, (3) ff is a map N ! N , (4) ¯ is a map N ! f"; ; #; ##;###; : : : ; # n (n 1)g, (5) is a map N ! f"; g , such that for all x 2 G, dom(ff(x)) = dom((x)) 2 SeqN. Informally, for each node we have its node symbol oe(x) and its sequence of successors ff(x). The node carries a node marking ¯(x), and each arc to a successor (say the k th , ff(x)[k]) carries an arc marking, (x)[k]. The maps ¯; are referred to as the markings...