archives

Formalized Data Flow Diagrams and Their Relation to Other Computational Models


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Symanzik, Juergen and Baker, Albert L. (1997) Formalized Data Flow Diagrams and Their Relation to Other Computational Models. Technical Report TR96-20, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

Formalized Data Flow Diagrams and Their Relation to Other Computational Models
Juergen Symanzik and Albert L. Baker
One approach to the formalization of Data Flow Diagrams (DFD's)
is presented by Coleman and Leavens, et al. These Formalized Data Flow
Diagrams (FDFD's) can be viewed as another model of computation.
This paper contains an analysis of the computational power of these FDFD's.
We first consider the issue whether certain features of FDFD's affect their
computational power. A Reduced Data Flow Diagram (RDFD) is an FDFD with no
stores, finite domains for flow values, and no facility for testing for
empty flows, but it may contain persistent flows. An RDFD without persistent
flows is called a persistent flow--free Reduced Data Flow Diagram (PFF--RDFD).
We show that PFF--RDFD's are Turing equivalent. The other features of FDFD's
only add to the expressive power of FDFD's. Therefore, any FDFD can be
expressed as an PFF--RDFD.
Our proof that PFF--RDFD's are Turing equivalent procedes as follows.
We first show that any RDFD can be simulated by a FIFO Petri Net.
We then show that any Program Machine can be simulated by an PFF--RDFD.
It is known that FIFO Petri Nets and Program Machines both are Turing
equivalent.

Subjects:All uncategorized technical reports
ID code:00000143
Deposited by:Staff Account on 25 April 1997



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