Specification of concurrent systems using graph grammars
Loyall, Joseph Patrick
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/19683
Description
Title
Specification of concurrent systems using graph grammars
Author(s)
Loyall, Joseph Patrick
Issue Date
1991
Doctoral Committee Chair(s)
Kaplan, Simon M.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
Existing textual programming languages support sequential programming well because there is a correlation between the one-dimensional nature of text and the one-dimensional nature of sequential programs, i.e. the single flow of control in a program. Textual notation does not support concurrent programming as well, however, because concurrent programs have many threads of control, have a two-dimensional relationship between the flow of control in a process and the flow of information between processes, and are often dynamic. Most existing models for the specification of concurrent systems support one or two of these traits, but fall short of supporting all three.
Graph grammars are well suited for the specification of concurrent systems because they are also inherently concurrent, two-dimensional, and dynamic. We have developed a general graph rewriting model, $\Delta$-grammars, based on the theory of graph grammars. Concurrent systems are specified in A by representing the state of the system as a graph and state transitions as graph transformations. Previously, we have developed a formal semantics for $\Delta$-grammars and demonstrated its usefulness for giving a graphical semantics of existing concurrent languages, such as Actors and GARP.
This thesis shows $\Delta$'s usefulness as a specification language. It describes how specifications are modularly and systematically designed in $\Delta$. It also describes a technique for the static analysis of $\Delta$-specifications. Classes of $\Delta$-specifications that are confluent, terminating, deadlock-free, starvation-free, or efficient to execute are recognized by examining the structure of $\Delta$-productions and the way in which $\Delta$-productions interact, both with other $\Delta$-productions and with state graphs. The technique for static analysis can be used to analyze existing $\Delta$-specifications and as a guideline for the design of correct $\Delta$-specifications.
The techniques are illustrated throughout with examples and tutorial introductions to graph grammars and $\Delta$-grammars are included.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
