On Schematological Equivalence of Dataflow Networks

AbstractWe consider the problem of determining when two dataflow networks with uninterpreted nodes always have the same input-output behavior. We define a set of behavior-preserving transformations on networks and show that this set is “schematologically complete”; i.e., networks have the same input-output behavior under all interpretations if and only if they can be transformed into isomorphic networks. As a by product, we obtain a polynomial algorithm for deciding schematological equivalence of dataflow networks