Irreducible Decompositions of Transformation Graphs by Assignment Techniques

Abstract—Autonomous sequential networks are represented by transformation graphs, i.e., finite directed graphs, each vertex of which has outdegree one. A network that can be realized by a set of simpler, parallel networks corresponds to a transformation graph representable as a Cartesian product of simpler graphs. An algorithm for obtaining the various decompositions of a given transformation graph into irreducible factors is presented. The particular decomposition into a minimum number of factors is directly reached by the method. Decompositions into a greater number of factors are also obtained so that a balance may be struck between number and complexity of factors.