On Metapaths in Metagraphs
Karel Čulík · SIAM Journal on Algebraic and Discrete Methods · 1984
Data graphs without (DG) or with (DGP) predicates are directed graphs with labeled vertices and edges. They reflect data flow algorithms if their inner vertices are interpreted by functions or predicates and their roots are initialized by some values. A metapath is an execution sequence of directed shrubs reflecting functions or predicates together with their argument positions. Acyclic data graphs generalizing terms and conditional terms are investigated. A data graph is functional if for each initialization all metapaths determine the same resultation. A finite acyclic DG is functional iff each inner vertex of its simplification DG* has exactly one shrub, where DG* is a data homomorphic image such that each data homomorphic image DG** of DG* is isomorphic with DG*. A finite acyclic DGP is functional iff any two shrubs of an inner vertex of its simplification are incompatible, i.e., they cannot be obtained by the same execution sequence. In the general case of nonacyclic data graphs the (serial) permit execution rule is formulated.