Timed data flow diagrams

Abstract

<p>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.</p>