Timed data flow diagrams

Thumbnail Image
Date
1996
Authors
Symanzik, Jürgen
Major Professor
Advisor
Herbert T. David
Albert L. Baker
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Statistics
Abstract

Traditional Data Flow Diagrams (DFD's) are the cornerstone of the software development methodology known as "Structured Analysis" (SA), and they are probably the most widely used specification technique in industry today. DFD's are popular because of their graphical representation and their hierarchical structure. Thus, they are well-suited for users with non-technical backgrounds and are commonly used to depict the static structure of information flow in a system. Numerous attempts to formalize DFD's have appeared in the technical literature. We focus on the Formalized Data Flow Diagrams (FDFD's) developed by Coleman, Wahls, Baker, and Leavens;This dissertation analyzes and extends FDFD's with respect to their usefulness in specifying the qualitative and quantitative properties of real systems. Prior to this dissertation, there existed no well-founded knowledge about the computational power of FDFD's nor any formal model in FDFD's of the timing behavior of real systems;The dissertation is organized as a collection of five independent papers. Briefly, the main results of each paper are as follows: (i) Reduced FDFD's are Turing equivalent. (ii) Stores, persistent flows, tests for empty flows, and infinite domains are not essential for FDFD's. (iii) Subclasses of FDFD's are equivalent to known subclasses of FIFO Petri Nets, immediately furnishing the decidability results for subclasses of FIFO Petri Nets to the corresponding subclasses of FDFD's. (iv) A general stochastic model of time for FDFD's (called Timed Data Flow Diagrams--TDFD's) is defined, allowing not only a description of the relative likelihoods of various execution times, but also descriptions of the possible joint firing behavior of transitions. (v) An aggregation principle can be used for an efficient stochastic analysis of periodic TDFD's with Markovian transition times;The results in this dissertation provide a firm theoretical foundation for further advances in Computer Science and Statistics, leading to practical and expressive tools for the specification and analysis of real systems.

Comments
Description
Keywords
Citation
Source
Copyright
Mon Jan 01 00:00:00 UTC 1996