Z EXPRESSIONS IN DIRECTED GRAPHS
Original Publication Date: 1976-Nov-30
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Schneider, Edward A.: AUTHOR [+2]
Z EXPRESSIONS I N DIRECTED GRAPHS Edward A. Schneider
Z EXPRESSIONS I N DIRECTED GRAPHS
Edward A. Schneider
Technical Report #76-12
Department of Compb, -- Science
Iowa State Universir, Ames, Iowa
This paper characterizes the class of directed graphs which can be expressed using a notation with single entry, single exit constructs.
A representative notation, called restricted regular expressions, is used. Those directed graphs which can't: be expressed as restricted regular expressions are found to be exactly those with a Z expression from the initial node to the final node of the graph.
Many concepts in computing can be represented using a directed
graph with names on each arc. For example, the control paths of a program can be thought of as a directed graph with the arcs named by functions which change the data. These graphs are frequently called flowcharts. Similarly, the synchronization of operations i n a parallel program can be expressed as a directed graph . The arcs are labeled by the operation names and indicate the. sequences which can be allowed. The named' directed graph:
expresses the requirement that the operations write" and "read" must alternate.
While directed graphs sometimes art? a good tool to help picture a computing concept, their two dimensional nature makes them difficult
to use in a computer language. Instead, some other notation, such as IF-THEN-EILSE and WHILE-DO statements for program control paths, is used. If the notation is w e l l chosen, the structure represented w i l l usually remain clear.
One property that is necessary for this clarity is that each arc
be represented only once i n the notation. By this is meant that if each arc has a different name, then a name should only be used once. Other- wise, the overall structure of the graph w i l l be broken up and hard to understand. The possibility for error w i l l also be increased. In order to concentrate on the correspondence between the structure of the graph and its representation in a notation, in what follows the assumption w i l l be made that each arc has a different name.
Formally, a directed graph is a 4-tuple (V,A,A,p) where V is the set of nodes, A is the set of names, A: A+VxV is a function associating each name with an arc, and psV is the initial node. The notation (u,v) w i l l be used to represent an arc from u to v. A path progression is a sequence of n arcs (v ,vl)(v ,v 1.. v n , v such o 1 2 n
that v #v and no arc is repeated. For example, the directed graph: