Formalized Data Flow Diagrams and Their Relation to Other Computational Models

Thumbnail Image
Symanzik, Jürgen
Baker, Albert
Major Professor
Committee Member
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence

Related Units

Journal Issue
Is Version Of

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.


© Copyright 1996 by Jürgen Symanzik and Albert L. Baker. All rights reserved.

Subject Categories