Theory for Graph-Based Language Specification, Analysis, and Mapping with Application to the Development of Parallel Software.

摘要

This dissertation develops a generalized formal language theory model and associated theorems for the specification, analysis, and mapping of graphs and graph-based languages. The developed model, defined as a graph generative system, is analyzed from a set theoretic, formal language, algebraic, and abstract automata perspective. As a result of the analysis, numerous theorems pertaining to the properties of the model, graphs, and graph-based languages are derived. The graph generative system model also serves as the basis for applying graph based languages to areas such as the specification and design of software and visual programming. The specific application area emphasized is the use of graph-based languages as user-friendly interfaces for wide-spectrum languages that include structures for representing parallelism. The goal of this approach is to provide an effective, efficient, and formal method for the specification, design, and rapid prototyping of parallel software. To demonstrate the theory's utility and the feasibility of the application, two models of parallel computation are chosen. The widely used Petri net model of parallel computation is formalized as a graph-based language. The Petri net syntax is formally mapped into the corresponding syntax of a Communicating Sequential Processes(CSP) model of parallel computation where CSP is used as the formalism for extended wide-spectrum languages. Finally, the Petri net to CSP mapping is analyzed to demonstrate that the CSP specification formally behaves in a manner equivalent to the Petri net model. High level languages; Information theory; Parallel processing; Programming language translation, Theses. (edc)