

Symanzik, Juergen and Baker, Albert L. (1997) Subclasses of Formalized Data Flow Diagrams: Monogeneous, Linear & Topologically Free Choice RDFD's. Technical Report TR9622, Department of Computer Science, Iowa State University.
Abstract
Subclasses of Formalized Data Flow Diagrams:
Monogeneous, Linear, and Topologically Free Choice RDFD's
Juergen Symanzik and Albert L. Baker
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.
Contact site administrator at: ssg@cs.iastate.edu
