Browse Prior Art Database

EXPRESSIONS IN DIRECTED GRAPHS

IP.com Disclosure Number: IPCOM000127993D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 12 page(s) / 33K

Publishing Venue

Software Patent Institute

Related People

Edward A. Schneider: AUTHOR [+3]

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 text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

EXPRESSIONS IN DIRECTED GRAPHS

by

' Edward A. Schneider

Technical Report #76-12 Department of Compu. -- Science Iowa State UniversiL,, Ames, Iowa November 1976

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.

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 in 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: write

read expresses the requirement that the operations "write" and "read" must alternate. While directed graphs sometimes are 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-ELSE and WHILE-DO statements for program control paths, is used. If the.notation is well chosen, the structure represented will usually remain clear. One property that is necessary for this clarity is that each arc be represented only once in 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 will be broken up and hard to understand. The possibility for error will 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 will be made that each arc has a different name. Formally, a directed graph is a 4-tuple

(Equation Omitted)

where V is the set of nodes, A is the set of names,

(Equation Omitted)

Iowa State University Page 1 Dec 31, 1976

Page 2 of 12

EXPRESSIONS IN DIRECTED GRAPHS

is a function associating each name with an arc, and peV is the initial node. The notation (u,v) will be used to represent an arc from a to v. A path progression is a sequence of n arcs

(Equation Omitted)

such that

(Equation Omitted)

and no arc is repeated. For example, the directed graph:

(Equation Omitted)

B

is represented as

(Equation Omitted)

where

(Equation Omitted)

is a path progression from a to w. A restriction which is usually made in a notation is that the various constructs have exactly one entry point and one exit point. This also implies that they can't be used in an overlapping manner but must eit...