Technical Report Number
Theory of Computation, Computing Methodologies
Formalized Data Flow Diagrams (FDFD's) and, especially, Reduced Data Flow Diagrams (RDFD's) are Turing equivalent (Symanzik and Baker, 1996). Therefore, no decidability problem can be solved for FDFD's in general. However, it is possible to define subclasses of FDFD's for which decidability problems can be answered. In this paper we will define 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 (Kasai and Miller, 1982). 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.