Subclasses of Formalized Data Flow Diagrams: Monogeneous, Linear & Topologically Free Choice RDFD's
Jürgen Symanzik, Albert L. Baker · 1996
Formalized Data Flow Diagrams (FDFD's) and, especially, Reduced Data Flow Diagrams (RDFD's) are Turing equivalent ([SB96a]). Therefore, no decidability problem can be solved for FDFD's in general. However, it is possible to de ne subclasses of FDFD's for which decidability problems can be answered. In this paper we will de ne certain subclasses of FDFD's, which we call Monogeneous RDFD's, Linear RDFD's, and Topologically Free Choice RDFD's. We will show that two of these three subclasses of FDFD's can be simulated via isomorphism by the correspondingly named subclasses of FIFO Petri Nets. It is known that isomorphisms between computation systems guarantee the same answers to corresponding decidability problems (e. g., reachability, deadlock, liveness) in the two systems ([KM82]). This means that problems where it is known that they can (not) be solved for a subclass of FIFO Petri Nets it follows immediately that the same problems can (not) be solved for the correspondingly named subclass of FDFD's.