Formalized Data Flow Diagrams and Their Relation to Other Computational Models

dc.contributor.author Symanzik, Jürgen
dc.contributor.author Baker, Albert
dc.contributor.department Computer Science
dc.date 2018-02-13T23:11:03.000
dc.date.accessioned 2020-06-30T01:55:30Z
dc.date.available 2020-06-30T01:55:30Z
dc.date.issued 1996-12-01
dc.description.abstract <p>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.</p>
dc.description.comments <p>© Copyright 1996 by Jürgen Symanzik and Albert L. Baker. All rights reserved.</p>
dc.identifier archive/lib.dr.iastate.edu/cs_techreports/167/
dc.identifier.articleid 1163
dc.identifier.contextkey 5408187
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath cs_techreports/167
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/19980
dc.source.bitstream archive/lib.dr.iastate.edu/cs_techreports/167/TR96_20.pdf|||Fri Jan 14 21:04:27 UTC 2022
dc.subject.disciplines Theory and Algorithms
dc.subject.keywords Computational Power
dc.subject.keywords Turing Machine
dc.subject.keywords FIFO Petri Net
dc.subject.keywords Program Machine
dc.title Formalized Data Flow Diagrams and Their Relation to Other Computational Models
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
TR96_20.pdf
Size:
287.81 KB
Format:
Adobe Portable Document Format
Description:
Collections