Browse Prior Art Database

Z EXPRESSIONS IN DIRECTED GRAPHS

IP.com Disclosure Number: IPCOM000148425D
Original Publication Date: 1976-Nov-30
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Schneider, Edward A.: AUTHOR [+2]

Abstract

Z EXPRESSIONS I N DIRECTED GRAPHS Edward A. Schneider

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 24

Z EXPRESSIONS I N DIRECTED GRAPHS

Edward A. Schneider

Technical Report #76-12

Department of Compb, -- Science

Iowa State Universir, Ames, Iowa

November 1976

[This page contains 1 picture or other non-text object]

Page 2 of 24

[This page contains 1 picture or other non-text object]

Page 3 of 24

ABSTRACT

   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.

[This page contains 1 picture or other non-text object]

Page 4 of 24

[This page contains 1 picture or other non-text object]

Page 5 of 24

1. Introduction


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 [6]. The arcs are labeled by the operation names and indicate the. sequences which can be allowed. The named' directed graph:

read

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.

It

[This page contains 1 picture or other non-text object]

Page 6 of 24

    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:

0 n

is represented...