Subclasses of Formalized Data Flow Diagrams: Monogeneous, Linear & Topologically Free Choice RDFD's

Symanzik, Juergen and Baker, Albert L. (1997) Subclasses of Formalized Data Flow Diagrams: Monogeneous, Linear & Topologically Free Choice RDFD's. Technical Report TR96-22, 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.


Subjects:
All uncategorized technical reports


ID code:
00000141
Deposited by:
Staff Account on 25 April 1997





Contact site administrator at: ssg@cs.iastate.edu