rDi-ssertatéan far thefieg'riee of" FEL‘D;
MECHtGfifi STATE‘UNE‘ERSETY g
m: CHRISTEAH é’u’kNSEfi , ‘
' 1974

 

 

This is to certify that the

thesis entitled

STRULTUKGL PROPERTlES

John

DateWLfi/y

0-7639

OP PRocesses

presented by

C hris‘hln Hansen

has been accepted towards fulfillment
of the requirements for

M degree in Q’éfi‘L" {" ‘W

flag/s»;

Major professor

 

 

 

   
 

   

jig,“ ‘7 3.7: i '
nuns & sous
T 300K BINUERI lNE.‘
LIBRARY amoms
ERNIE”, “II“;

w

 

 

 

 

ABSTRACT
STRUCTURAL PROPERTIES OF PROCESSES
By

John Christian Hansen

In this thesis, a definition of process, which is both
mathematicalbrprecise and practically significant, is prOposed.
Using this definition, a theory of process decomposition, which
is similar to that which Hartmanis and Stearns (HART 66) develOp
for sequential machines, is prOposed. A necessary and sufficient
condition for the existance of such decompositions is shown.

A parallel decomposition theory more akin to that which
might be useful in parallel processing is also discussed. It is
shown that there is no algorithm which will detect all cases of
this kind of parallelism. However, sufficient conditions for the
existance of this kind of decomposition are given.

This thesis also points out how digraph theory serves
as a productive tool in the analysis of processes. A special digraph
is associated with each process. This digraph is used in the derivation
of sufficient conditions for process termination. It also provides
the basis for the determination of both computational cost measures
and process cost measures. These measures provide the motivation

for the develOpment of a general theory of digraph measurement. The

'0 John Christian Hansen
z\ general theory is shown to have some well-known measures as
Special cases, as well as being the foundation for the deve10p-

ment of several new useful measures.

STRUCTURAL PROPERPIES OF PROCESSES

By

John Christian Hansen

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements

for the degree of

DOCTOR OF PHILOSOPHY

Department of Computer Science

MY PARENTS

ii

ACKNOl'JIEIXll-iEN‘I‘S

I am grateful to Dr. Merteza A. Rahimi, my thesis
adviser, for his encouragement during the course of this thesis.
My thanks also go to Dr. Harry Hedges, Dr. Lewis Greenberg, Dr.
Carl V. Page, Dr. Edgar M. Palmer, and Dr. Edward A. Nordhaus for
serving on my guidance committee and for their critical review
of this work. My special thanks go to my typist, Debbie Claflin,
for her Speed and accuracy in typing the final draft.

Finally, I am deeply indebted to my wife, Elizabeth,
for her critical review of this work which improved the eXposition

by at least an order of magnitude.

iii

TABLE OF CONTENTS

Chapter 1: Introduction and Literature Review
Chapter 2: Processes
2.1: Definitions
2.2: Detection of Parallelism
2.3: Detection of Non—trivial Parallelism
Chapter 3: Sufficient Conditions for Possession of
an Infinite Computation
Chapter #: Measures of Process Cost
h.l: Computational Cost
4.2: The Cost of a Process
Chapter 5: A General Theory of Digraph Measurement
5.1: A Discussion of L and Norms on L
5.2: The Importance of Strong Norms
5.3: Associating Non-negative Real Numbers with
Digraphs
Chapter 6: Applications of the General Theory
6.1: Balance in Signed Digraphs

6.2: Cost of Retrieval from a Binary Tree

6.3: A Measure of Transitivity

6.#: A Measure of Symmetry

iv

page

19

39
53
53
58
65
6S
68

73
78
78
82
8.5,

90

Chapter 7: Summary and Future Research

7.1: Summary 96
7.2: Future Research 97
Appendix 100
List of References 104

Chapter 1

INTRODUCTION AND LITERATURE REVIEW

The topics covered in this thesis fall into four major
categories; a precise definition of process and the resultant theory,
associating digraphs with processes, the concept of measurement in
a process, and a generalization of these results to measures on
digraphs in general.

Central to the develOpment of computer science theory
is the concept of process. P. Brinch Hansen (BRIN 70),E.w.
Dijkstra (KIJK 68), J.H. Saltzer (SALT 66) and others have suc-
cessfully used the concept of process as a basic unit in their
descriptions of complex computer systems. Zohar Manna (MANN 70),
C.V. Ramamoorthy and M.J. Gonzales (GONZ 70), Leslie Lamport
(le2 7+), M. Lenman (mm 68), J.B. Dennis (DENN 66), D. Knuth
(KNUT 66), and others have successfully used the concept of process
as a basic unit from a programming languages standpoint.

A survey of the literature shows that there is a lack of
any agreement on a single definition of process. In (DENN 66),

Dennis and Van Horn state that:

...a process is that abstract entity which moves
through the instructions of a procedure as the
procedure is executed by a processor.

1

In (GILB 72), Gilbert and Chandler view the system of processes as

follows:

...an individual process is approximated by an
abstract process which consists of distinct
portions or 'states'. A set of such states, to—
gether with a set of values of data variables,
then approximates of configuration (or com-
posite state of an entire system or process.
The 'moves of individual processes from
one state to the next are written as abstract
partial rules. Partial rules fer the differ-
ent individual processes may then be combined
to yield transition rules - moves from one
composite state to a next - for the entire
system of processes.

In (DAHL 66), Dahl and Hygaard in describing SIMULA, an ALGOL based

simubtion language, take the following view of process:

In general a process has two aspects: it is
a data carrier and it will execute actions.

In(DENN 66), a process is considered to be the status of a system,
in (GILB 72) a sequence of such status values, and in (DAHL 66) as
a generator of such sequences.

While Gilbert and Chandler (GILB 72) also consider "trans-
ition rules", it was Horning and Randell (HORN 73) who first combined
all these notions in a single definition of process. Horning and Ran-
dell define a process as a triple (S,f,s) where S is a state space,

f is an action function in that Space, and siis a subset of S which
defines the initial states of the process. By action function, they

mean a relation on the Cartesian product of s and the set of all

3

possible actions. By actions, they mean assignments to variables in the
state Space.

While the definition of Horning and Randell is mathematically
precise, it appears to be too general. It suffers from the fact that
f may not even be computable and from its lack of relation to common
process specifications (i.e. - algorithms, flowcharts, and programming
languages). In this thesis, a definition like that of Horning and
Randell isuused but f is replaced by a flowchart-like diagram similar
to those disucssed by I. Nassi and B. Schneiderman (NASS 73), It is
hoped that the resultant definition has both the mathematical precision
and the practical significance to become a useful tool.

Once a definition of process is agreed upon, the concept
pf parallel processing may be discussed. It is helpful to distinguish
between two types of parallel processing; multiprocessing and multi-
programming. Multiprocessing is a simultaneous sharing of two or more
portions of the same program by two or more processing units. £31517
proggammigg is the time and resource sharing of a computer system by
two or more programs which reside simultaneously in primary memory.

There are two basic ways one may handle multiprocessing of
a program; new programming language concepts may be introduced or
parallelism may be automatically detected at the compiler level.
ALGOL~68 (VANN 69) has incorporated parallelism concepts in its
definitions. At the statement level, this is done by replacing ';'
with ',' and at the procedure level by using a par symbol. At the
assembly level, Dennis and Van Horn in (DENN 66) suggest the FORK-

JOIN-QUIT combination:

n

The basic primitive Operation of parallel
programming is implemented by the meta-
instruction FORK w ; ... where w is a word
name. A FORK meta-instruction indicates
a new process at the instruction labeled
w. The newly created branch process is
part of the same computation as its creator
or main process...

A process that has completed a se-
quence of procedure steps is terminated
by the meta-instruction QUIT after which
the process no longer exists...We use the
instruction JOIN T,w; which is essentially
Conway's join instruction. Here T is the word
name of the count to be decremented and w
is the word name of an instruction word to
be executed if the count becomes zero.

A number of attempts have already been made to auto-
matically detect parallelism. Summaries of attempts to detect
parallelism at the statement level may be found in (BAER 68). Bernr
stein (BERN 66) was the first to attack the problem of detecting
parallelism at the interstatement level. His model may be simply
stated as follows; suppose there are two statements in a programming
language, P1 and P2, which were originally scheduled in sequence.
The conditions under which P1 and P2 may be executed in parallel
are as follows:

1) 11n02=¢

2) 12n01=¢

3) 01 [1 02 = d

where Ii and 01 represent, reSpectively, the input (those variables
which appear only at the right of an assignment statement) and the
output data sets of Pi'

Based on these conditions, systems that automatically

detect parallelism have been written. Examples may be found in

5
(RUSS 69), (VOLA 7o), (RAMA 69), and (BING 67). Detection of
parallelism in D0 leaps is not quite as simple. Such analysis is
carried out with some success by Bernstein (BERN 66), Russel (RUSS 69),
and by Lamport (LAMP 7%). The decomposition theory in this thesis
suggests a method for automatic detection of parallelism. The concept
of diagram as introduced in this thesis is closely related to a parallel
programming language.

Normally, measurement and process are associated with
computational complexity. Historically, the question of computa-
tional complexity grew from the origin of computability. One way
to define computability is to say that a function is computable if
it is possible to obtain it from a finite number of Operations of
composition, primitive recursion or application of the.A&-0perator
to regular functions starting with the functions:

1) 3(x) - x + 1

2) N(x) = O

3) If; (x1,...,xn) - xi (1g 19).

Primitive recursion may be represented by the conditional expression
notation, first introduced by McCarthy (MCCA 60). Conditional
expressions will be written in the form:

(B1—~e1, b -0e b

2 2,...

where bi denotes a Boolean expression. The value of the conditional

11-1“ en-‘l ’ an)

expression is obtained by examining bi's in turn from the left until
one is found which is true; the value for the expression is ei if bi
is true. If no true bi's are found, the value for the expression is

en. In this notation, the definition of the factorial function might

be written:

6

fac(n) = ((n+O)-') l, n-fac(n-l)).

To put the preceding into historical perSpective, Church
(CHUR 36) in 1936 eXpressed the opinion that the concepts of }K-
definable functions and recursive functions are both identifiable
with the concept of computable function (Church's thesis). In the
same paper, he showed that the decision problem for the predicate
calculus is unsolvable. The same was proved by A.M. Turing (TURI 37)
at about the same time. Turing introduced the concept of what is now
known as Turing machine for his proof.

Once the concept of computability has been defined, then
the question of how to characterize the complexity of computable
functions arises. The most familiar ways of doing this are; by
the number of steps needed to compute a function (HART 6A, HART 65)
and by the amount of memory needed for a computation (HART 65 b).

A machine independent theory of the complexity of recursive functions
is presented in (BLUM 67).

It should be noted that all results in complexity theory
deal with classes of functions rather than measures for individual
functions. Thus for example, the theory of Turing machine complexity
classes may shed some light on the preperties of languages that are
suitable as programming languages (i.e. - languages that can be
simply recognized) but it is of little use in extracting information
about a particular language (other than the class to which it belongs).

Several interesting observations have been made about
complexity classes. Every set accepted by a time or tape-bounded
Turing machine is a recursive set. Furthermore, every recursive set
is accepted by some tape-bounded Turing machine and also by some time-

bounded Turing machine. Since no complexity class can contain all

7

recursive sets, there must be an infinite hierarchy of complexity

classes. Lewis in (LEWI 71) makes the following observation:

Quite often when pathological problems exist in
complexity hierarchies, it has been shown that
they exist only in the lower levels of the hier-
archy...Conditions that occur in all but a finite
number of places are accepted in automata theory
as being desirable in most cases...

But, in complexity hierarchies, the functions
which are easiest to compute, and that are computed
most often, occur at the bottom. These very func-
tions are the ones computed in "real-life" and
therefore are quite important.

In this thesis, measures involving processes are for
the most part concerned with individual processes rather than
classes of processes, hence computational complexity does not
play a central role. However, when some of the results are gener-
alized to results involving digraphs, a theory which has some
parallel with complexity theory is developed. Rather than ordering
the computable functions into complexity hierarchies, a theory
for ordering members within a class of digraphs is developed.

Digraph theory serves as a productive tool in a number of
areas in computer science. This stems from the fact that digraph
theory deals with the structural preperties of empirical systems. Such
theory is bound to find applications in a discipline so full of
structure as computer science.

Harary, Norman, and Cartwright (HARA 65) define a
digraph as a net with no lOOpS or parallel lines. A net has four
primitive (undefined terms) and two axioms. The four primitives

of nets (also of digraphs) are:

8

’U

a set V of elements called vertices.

O.

a set X of elements called lines.

'U

a function f whose domain is X and whose range is contained

in V.

a function 5 whose domain is X and whose range is contained
in V.

The axioms for a net are:

A1 : the set V is finite and not empty.

A : the set X is finite.

2
Primitives P3 and Ph relate the lines to the points. They give
the first and second point of each line.

In this thesis, a less restricted definition of digraph shall
be used. A digraph $111 be a structure which satisfies P1 through P1+
and the following axioms:

A1 : the set V is not empty.

A2 : there are no parallel lines (Two lines, x and x are

1 2’

parallel if F(x1) = f(x2) and s(x1) = s(x2) )

Thus, a digraph may have an infinite number of points or lines and
may contain 100ps. Digraphs will be used to determine sufficient

conditions for the termination of processes. Also, a framework

for measuring certain graph-theoretic preperties will be develOped.

Chapter 2

PROCESSES

In this chapter, the concept of process is introduced.
Section One deals with the basic definitions and descriptive theo-
rems. In Section Two, a parallel decomposition theory similar to
that of Hartmanis and Stearns (HART 66) is develOped. In section
Three, the problem of nontrivial parallelism is addressed. It is
shown that the best results obtainable are sufficient conditions

for decomposition.

2.1 DEFINITIONS

As stated in Chapter One, the approach here is strongly

influenced by the definition of process given in Horning and Randel

 

 

(HORN 73).

Definition 2.1. A state variable is an elementary quantity
which can assume certain well-defined values.

Definition 2.2. A set of labeled state variables constitutes a

 

state variable set.

10
Definition 2.3. An assignment of values to all variables in

a state variable set defines a state of the set.

Definition 2.#. The set of possible states for a given state

variable set is the state space of that set.

Exam131e 2.1. Consider the state variable set V = {am}
consisting of two variables labeled a and b whose values may be any
natural number. If a is assigned the value 5 and b the value 7,
this defines the state (a=5,b=7). The state space of this variable

set is S(V) - i(a=m,b=n)' m>0, n’O) '

Example 2.2. The state variable set of a typical C.P.U. might
include all registers and all memory locations. The state space for

this set would be all possible combinations of values of these variables.

Definition 2.5. A computation in a state Space is a sequence of

states from that Space.

Definition 2.6. The first element of a computation is called its

initial state.

Definition 2.7. The last element of a finite computation is called

its final state.

Example 2.3. Consider the state Space of Example 1, the se-

quence C1 = 1<L(a=2,b=l),(a=2,b=2),(a=2,b=3),(a=2,b=4);> is a

ll
finite computation for which the initial state is (a=2,b=l) and the
final state is (a=2,b=#). An example of an infinite computation in
the same state space is the sequence Ca = 4<fia=2,b=n) n=l,2,3...;>-

Its initial state is (2,1) but it has no final state.

The concept of computation is essential to the definition of process .
There are, of course, many ways in which a particular computation may
be specified. The form in which most computations will be presented

in this thesis is in terms of the transitions which occur between

states.

Definition 2.8. An action in a state Space is a finite set of
assignments of values to some of the variables

of its state variable set.

Definition 2.9. If a state is followed by an action, then the
immediate successor of the state is the new
state whose variables all have their old values
except those which have new values assigned by
the action.

Example 2.4. If (x=3,y=5) is followed by the action {Lye-#3 ,

its immediate successor is (x=3,y=4).

Definition 2.10. The null action is the action which Specifies

no assignments.

12
In this thesis, actions will be represented in pictorial
form by action boxes. The method used is an adaptation of a system
of flowcharting develOped by I. Nassi and B. Shneiderman (NASS 73).
Their system was an alternative to conventional flowchart languages
and designed to be more amenable to structured programs.
An action whose cardinality is one, such as the action

of Example 2.4. would be represented like this:

 

ydr—4

 

 

 

Fig 2.1

Actions whose cardinality is greater than one will be denoted by:

 

 

 

Ant-'2 [B 4-“1 ) (3(-Ht Die—-x E ¢-7

 

 

 

 

 

 

 

Fig 2.2

The assignments must not have variables left of an arrow
in common. For example, an action may not contain both X4-Y + Z
and X<—- 7. All expressions right of an arrow are calculated and
all assignments of an action are made simultaneously. Any reference
to a state variable right of an arrow refers to its value.

If one of two basic digrams are to be performed, depending

upon the value of some boolean expression, the If clause may be used:

13

 

 

 

 

 

 

Fig 2.3

The central triangle contains a Boolean expression, the left and
right triangles contains a T or an F to represent the possible
outcomes and A and A are basic diagrams.

1 2

Example 2.5. If the state (a=1,b=2,c=3) is followed by:

 

 

 

 

 

 

 

Fig 2.4

the result is the state (a=3,b=2,c=3).

To allow for iteration, the DO while clause may be used:

k

DO while B —_l

[A I

Fig 205

l#
A is a basic diagram and B is a Boolean expression. The actions
in the basic diagram are performed while B is true. A §a_s_i_g
digggam consists of any of the symbols introduced so far, including
the DO while clause, stacked one upon the other.
Before formally defining process, a few examples are in

order.

Example 2.6. This example involves matrix multiplication. A and

B are NKN matrices and the product C is an NXN matrix.

 

 

 

 

 

 

re—1
DO while 12 Al' N
J4—1
Dewhile J‘N
suns—o ice—1

 

 

DO while K £§ N

 

SUM ‘F" SUM +

A(I,K) . B(K,J)

 

 

K 4b" K + 1

 

C(I,J) e-—- sun

 

 

J"t- J + 1

 

I 4r- I + 1

 

 

 

 

Fig 2.6

15
This example shows how the concept of process may

 

 

 

 

 

 

 

 

 

Example 2.7.
be used to model a continuous phenomenon.
T (h-<D
DO while T 2’.- 10
D'(-—’§5 ‘ T
{P 4P-'TP + .01
Fig 2.7

T may be thought of as time and

The state variables are D and T.
D as some instantaneous object whose 'snapshot' is being taken from

T=O through T=1O in increments of .01.

The formal definition of process in now given.

Definition 2.11. A process is a triple (S,d,I) where S is a
state Space, I is a subset of S, and d is a

basic diagram.

The final (initial) states of a process are the

Definition 2.12.
final (initial) states of all of its computations.

A diagram is made up of basic diagrams stacked

Definition 2.13.
in parallel as follows:

Definition 2.14.

16

 

Fig 2.8

A diagram must be finite and the Di must

have no state variables in common.

A combined pgocess is a triple (S,d,I) where
S is a state Space, I is a subset of S, and

d is a diagram.

Given any basic diagram, labels may be associated with each

action box. These numbers will be useful in proving a number of

results about processes.

Definition 2.15.

Example 2.8.

 

The label of an action is its position in its basic
diagram (only actions are counted). Since each
basic diagram has only a finite number of positions,
it is possible to assign each when a number which

will be thought of as its label.

In the figure, there are 5 labels. The actions

in the body of the DO while clause are counted but not the clause

itself. The label of the action Gé—‘X + 3 is three.

l7

 

I ‘-" 1

DO while I 4- 1O

 

 

X €-—- I + 10

 

G €——' X + 3

 

I 4-' I + 1

 

 

A fir-—'G

 

 

 

Fig 2.9

Definition 2.16. For any process (S,d,I) let Ii be the set of
all states which can immediately precede actions
labeled i. (If a process has n labels, In+1

shall be used to denote its final states for sake

of completeness.)

Theorem 2.1. It is possible to translate a process into a

recursive function.

Proof
Each level n in the basic diagram of a process may be thought of as
a functiOn whose domain is In'

Suppose the basic diagram of the process is:

 

A

 

B

c
Fig 2.15

 

 

 

18
where A,B,C are actions. With each action can be associated a

function a, b, c.

 

 

 

 

 

 

A a(x)

B b(a(x))

C c(b(a(x))) where xzé I1
Fig 2.11

If clauses are handled in the following manner:

 

 

 

 

 

Fig 2.12

Let b(x) be the function associated with B, and a(x) the function
associated with A. The function f associated with the If clause
is f(x) = (b4b(x),a(x)).

Do while clauses are handled in the following manner:

 

DO while b

g

 

 

 

 

Fig 2.13

19
Suppose the basic diagram B has function e(x) and the next basic
diagram A has function a(x), then the function for the entire basic
diagram f(x) will be: f(x) = s(e(x)) where s(x) = (b-’f(x),a(x)).
If there is no basic diagram following the DO while clause then
f(x) = s(e(x)) where s(x) = (b-9’f(x), undefined).

This completes the proof.

Corollary. It is possible to translate a combined process
into a recursive function.
area:
Since the Di have no state variables in common, partition S
accordingly and construct the recursive function, fi, for each

separate process.
2.2. DETECTION OF PARALLELISM

In this section, a decomposition theory, along the lines
of that of Hartmanis and Stearns (HART 66) for sequential machines,
is developed for processes. A necessary and sufficient condition

for this type of parallelism is presented.

Definition 2.17. The parallel connection of two processes

P1 = (S1,d1,l1) and p2

combined process 19:131 ll P2=(S1x sZ,d,I1x12)

= (Sa,d2,I2) is the

where d is the following diagram:

2O

 

Fig 2.14

In order to study the parallel decomposition of processes,
P = (S,d,I), it is necessary to associate with the process a successor
function and with S N the concept of partition. (Where N is the

set of labels of d).

Definition 2.18. The successor function of a process P=(s,d,I)
is a function from SXN into SXN such that

(y,e) if x (the nth

level action) =y

f((x,n)) = and x£ In where e is the next label.
undefined otherwise

where x and y are in S, N is the set of levels

of P, and n is in N. (For convenience, N will

always contain one more label which will be

associated with final states.)

Definition 2.19. A partition.1T on the Cartesian produce of the
state Space and the labels of a process (S,d,I)
is said to have the substitution property iff
r3 tur) implies f(r):—.-: £(t)(fl ) for all r

and t in SJ‘N (where f is the successor function).

21
Definition 2.20. Let‘n‘ be a partition with the substitution
preperty on the Cartesian product of the state
Space and the labels of a process P = (S,d,I).
The T-ipgge of P is the process: P1“ =
(1' ,d‘ ,11 )where f" (B1 ) = 3:" iff
there exists x in B, such that f(x) 5 B;

(f'is the successor function of P“ .)

The last definition is correct becausc'l'l'has the sub-
stitution preperty iff f maps blocks of“ into blocks of‘n" .
0
(That is to say for B“- inTr there exists a unique Bll’ in"
I

such that f(Bfl )§ B n .) P“- may be thought of as a process

which does only part of the computation performed by P, since it
only keeps track of which block of‘ll' contains a particular state

of 3.

Example 2.9. Consider the following process P = (S,d,I)
where S is the set of natural numbers, f(x,1) = x+1, I =£13 ,

and d is:

 

DO while X > O

k

XQ'—X+1

 

 

 

Fig 2.15

suppose II = {(80,1),(B1,1)3 such that (x,1) is in (130,1) if

22

x is even and (x,l) is in B if x is odd. Clearly, TI has S.P.

1
(Take any two odd numbers x and y. f(x,1) is even and f(y,1) is
even so f(x,1) E f(y,1)(‘l1' ). The case for which both x and y
are even follows in the same manner.) E“. = (11' ,da , (B13 )

where in (BO) = B and f" (B1) = B .

1 0

Both P and P" produce a single infinite computation. P,T
may be thought of as a process which only computes whether or not
the number is odd or even, while P also computes the value of the
number. This can also be thought of in terms of ignorance of a state
of P. If“ has S.P. on P, by knowing P11 , the block of ‘l‘!
which contains a state of P is known, given a block of‘l‘l’ , the
block of ‘II’ to which the successor function will lead can be com-
puted. If a partition“ does not have S.P., then this computation
is not possible. So S.P. partitions define a sort of uncertainty
about the state of P which does not Spread as the machine operates.
(e.g. -in the above example, it is known if the number is odd or

even at any point in time.)

Theorem 2.2. If “'1 and 'W 2 are S.P. partitions onaa process
P = (S,d,I) then so are the partitions 171 ' 1T 2

‘lT1+Tl’2

Proof
Suppose rs t(1T1) and r-‘.=.-’ t(1T2), then by definition of'll'1 ° 17 2
r5 t( 1T1- u 2)
Now by the hypothesis of the theorem:
f(r) :-: f(t) (TF1) and

f(r) 2—2 f(t) (112)

23
but this implies f(r) .=.=.=. f(t) (Tr ,- 11“,.) by the definition of
fl1-‘fi'2 hence 1T1 .12 is an S.P. partition on P. To show
1'1 + “'2 has S.P., note that me t( 1T1 + 11'2) implies that

there exists a chain r = ro,r ,...,rm = t such that

1
rja: rj+1( 1V1) or rje. rj+1( 1T2) where 3 = O,l,...,m-1.
This shall be used to Show
r<r)=.:- f(t) (if 1 + 1(2).
Since W1 and ““2 have S.P., f(r)E f(r1)( 'W 1) or
-3

m1), f(r)(1T 2).
Since both "W1 and W2 are finer than 1" 1 == TI 2, it is evident
that f(r)::=. f(r1) (11’ 1 + 11' 2). In like manner:

f(r1)"=E f(r2)(-n_1 + TF2)

“rm-1):: f(t)( 1T1+TT 2)

hence, f(r)1"=' f(t) ( T1 1 + “2)
hence, 1T 1 + 1T2 has S.P.
Theorem 2.3. The set of all S.P. partitions on the Cartesian

 

product of the state Space and the labels of a
process P = (S,d,I) forms a lattice LP' under
the natural partition ordering. Furthermore,
LP contains the trivial partitions O and 1.
area:
From the last theorem, the set of all S.P. partitions is closed
under ‘ and + , thus it forms a sublattice of the lattice of all

partitions on SXN and hence is a lattice in the natural ordering

21+

of partitions. The last statement is trivial.

Definition 2.21. If P1 and P2 are two processes, then the function

G is said to be an assignment of P1 into P2 if:

i)“ is a one to one mapping of S1 x L.1 into
SZNL2 and

ii) f2 (9‘ (x)) = “(f1(x)) for all x in S1XL1.

 

 

Definition 2.22. Process P2 is said to realize the state behavior
of process P1 iff there exists an assignment of
P2 into P1.

Theorem 2.4. A process P.has a parallel decomposition of its

 

state behavior iff there exist two S.P. parti-

tions'n":I and TI 2 on P such that1T1‘1T2 = 0.

Proof
Let the state behavior of P be realized by P1 It P2. Leta be the

assignment such that at: SxL4(S1XK1)X(SZXL2). (L, L and

1!
L2 are the labels of P, P1, and P2 respectively.) 0‘ defines two
equivalence relations 11 1 and W2 on S XL as follows: r‘r—t( W1)
' = 0‘ :: '-
lff r1 t1 where (r) (r1,r2) and 0‘(t) - (t1,t2)

E = a : =
r t(TI'2) iff r2 t2 where (r) (r1,r2) and d(t) (t1,t2).
Since 0‘ is one-to-one:

s§t(1T1’-"2) implies S = t and hence, 1T1' W2 = 0.
To see that 7T1 and TI 2 have S.P., note that if r5 t( “1),

then fi‘(r) = (r1,r2) and “(U = (r1,t2) but this implies

25
that the first coalponents of the next states are identical hence,
f(r): f(t) (111).
The same argument shows‘lT 2 also has S.P.
To show the converse, assume that W1 and 11.2 are nontrivial
S.P. partitions on P such that 'l'l'1 ' 1T2 = 0. To construct

P and P let:

1 2
191:9,” =(Tl1,d"-1,I.“1)

Since 1T1 '1T2 = 0, each pair in ’YT1XW2 determines a unique

r in S! L.
2.}. DETECTION OF NON-TRIVIAL PARALLELISM

In this section, a number of sufficient conditons for the
parallel execution of the actions of a process will be given. The
theory develOped here differs from that of the previous section.
Here the question of how may the actions of a diagram be rearranged
so as to allow their parallel execution is considered. In the last
section, the question of how may the process be broken into dif-
ferent portions each operating on some segment of the state Space
was solved. To illustrate the difference, consider the following

two eprles .

Me 2.10. P = (S,d,I) where S = {(a,b,c) 1 a,b,c are natural

numbers} , I = (1,1,1) and d is:

 

 

 

 

 

 

 

 

 

 

 

aQ—‘ai-l 1 b(—-—-b+1

a «r—- a2 l b 4e—- c + b

ae—a-l J ce—b
Fig 2.16

By the theory deve10ped in the last section, P may be decomposed

into the following processes P1 = (S1,d1,I1) and P2 = ($2,d2,I2)

where S1 = {(a) 1 a is a natural number}

32 = {(b,c) \ b and c are natural numbers}
11 = (1) 12 = (1,1)
6.1 is:

 

:1 ‘k—- a + 1

 

aér—-a

 

aka-1

 

 

 

Fig 2.17

27
and d is:

 

b é-'b+1

 

b(—-c+b

 

c<—-b

 

 

 

Fig 2.18

It may not be evident at first that these two processes result
from the theory of the last section. To verify this, consider

these two partitions:

H
mm
v1

11.1 =63 1 (a1,b1,c1) and (a2,b2,c2) are in B iff a1

11-2 ={B 1 (a1,b1,c1) and (a2,b

ll

0'

E

II
13/

,c2) are in B iff b

2 1 2 1

Clearly 111' 112 = o. It is evident that P11' 1 = P and

1
P11. 2 = P2.
mm 2.11. P = (S,d,I) where S = ((a,b,c) 1 a,b,c are

natural numbers} , I (1,1,1) and d is:

 

a(—-2

 

b(---a+3

 

cfi—~4

 

c(-—--c+5

 

 

 

bQ—“2

 

Fig 2.19

28

I ' v
A process which does the same thing is P = (S,d,I) where d is:

 

Fig 2.20

Attention will now be turned to situations in which two
adjacent sections of a basic diagram may be performed in parallel,
as was the case in the last example. Unlike the previous section,

it is impossible to prove a theorem which completely characterizes

this kind of phenomenon.

Theorem 2.5. There is no algorithm which can decide if any

 

two sections of a diagram may be performed in

parallel 0

Proof
This assumption will be shown to imply a solution to the halting

problem for an arbitrary Turing machine T. Consider the following

class of diagrams:

29

    

 

  

T steps in
N or fewer
Operations

    

section 1

 

 

 

section 2

 

 

 

Fig 2.21

where N is an arbitrary integer stored on T's input tape. If

T never halts, then for all input data N, section 1 takes the

false branch and hence section 1 and section 2 may be performed

in parallel. If T eventually stOps, then there exists values Of

N for which section 1 takes the true branch. In this case, section
1 and section 2 must be performed sequentially. Thus, to see if
Section 1 and section 2 can be performed in parallel, the halting
problem must be solved.

The legality of the Boolean expression in section 1 of
the basic diagram may be questioned. SO far, it has been assumed
that any Boolean expression must deal with only variables in the
state Space. In order for the last theorem to make sense, there
Inust be a way for a process to Simulate a Turing machine. Bern-
stein (BERN 66) has a similar proof but ignores this question.
iHe makes no clear definition of process. At times he implies that
it is a segment Of statements from a program and at other times

implies that it is a Turing machine.

30

Defipition 2.2:. [Kl is the cardinality Of K.

Definition 2.2”: A( ‘11 , [K1 ) where I and K are finite sets,
denotes ]IHK\ variables.

Theorem 2.6. For an arbitrary Turing machine T, there exists a

 

process P which accepts an input string iff T does.

Given an arbitrary Turing machine T, a process shall be constructed
which is equivalent to it. For Turing machine T = (K,Z,F:6,q0,F)
construct the following process P = (S,d,I) where
s = (c,Dc( 11:1, 1r! ),oe< 1x1,|r'l)nw< m. In) ),w,E,T,J,A(l),A(2),...)
The values the variables may take on are:
l) C may take on any value from K or the special symbol U.
2) Dc(-,-) may taken on any value from K or the Special symbol U.
3) De -,-) may take on values from P-fiior the Special symbol U.
4) Dw(-,-) may take on values froméL,R,U} 0
5) u may take on values from{L,R,U}.
6) E may taken on values fromiL,R,U3'
7) T may take on values from the natural numbers.
8) J may take on values from r- {B3 or the special symbol U.
9) A(-) may taken on values from r. .
The initial states I of the process are all states which have the
following three prOpertiesz
1) C is qo.
2) MD for I from 1 to N for some natural number N, is not B
and the remaining A(-) are B.

3) Dc(-,-),De(-,-), and Dw(-,—) are assigned according to d? .
Ifxandyare inK, zis in F, ris inP-ZBSand
s is iniL,R)then if 5(x,z) = (y,r,s) , then

 

 

 

 

 

It is e.

31

Dc (x,z) = y

De (x,z) = r

D (x,z) = s
w

and if 5 (x,z) is undefined, then

Dc (x,z) = U
De (x,z) = U
Dw (x,z) = U

d is as follows:

 

 

T(--1l c<——-qO Ire—R

 

 

 

 

 

 

 

DO while E as U
C(—-DC(C,A(T)J Jé—Letc,A(T))| we-DW(C,A(T))
A(T) <-—- J

 

 

 

 

 

 

 

 

 

Fig 2.22

It is evident from the construction that the Turing machine and

the process do the same thing.

32

Corollary The concepts of Turing machine and process are
equivalent.
Proof

It follows from the above theorem and from Theorem 2.1.

Using the same techniques developed by Bernstein (BERN 66),
it is possible to analyse parallelism in processes. The state
variables of a state Space may be used in two ways by an action.
A state variable may only be referenced, in which case the state
variable is left unchanged. 0n the other hand, a state variable
may be changed. Clearly, if a state variable is on the left side
Of an arrow, it is changed and if it is on the right side Of an
arrow, it is referenced.

There are four different ways that a segment of a basic
diagram may use a state vanable.

l) The state variable is only referenced by the segment.

2) The state variable is only changed by the segment.

3) the first action involving this State variable is one in which
it is changed. One Of the succeeding actions references the
state variable.

4) The first action involving this state variable is one in which
it is changed. One Of the succeeding actions references the
state variable.

Let Ri’ci’Pi’ and Ki denote the sets of state variables
falling into these divisions reSpectively for section i. It is

evident that only a portion of the state variable set is modified

33
by a particular section i Of a basic diagram. That portion is
CiU PiU Ki' Also, the execution of section i depends only on
that portion Of the state variable set that is referenced by section
i. That portion is RiU Piu Ki' An important distinction must
be made between Ki in which the referenced state variable was com-
puted in section i itself and R1 and Pi in which the referenced
state variable has been assigned prior to section i. Consider the

following basic diagram (without D0 while clauses):

section 1]
section2l

Fig 2.23

 

 

 

 

The question is when may the above diagram be translated into the

following basic diagram:

 

 

section 1 1 section 2‘]

L.‘

 

 

 

 

 

 

 

 

Fig 2.24
Example 2.12. Consider the following diagram:

X (--“Y + Z
Z ‘ X I Y Section 1
Y‘fi-- Z
Q ar——-R + S

Section 2
P (-—IE + R
P 4--X *3 3 Section 3

 

 

 

Fig 2.25

34

It may be translated into

 

Fig 2.26

which is equivalent to:

 

Fig 2.27

The above example leads to the formal definition of the

jparallel connection of two adjacent sections of a diagram.

Definition 2.25. The pgrallel connection of two adjacent sections
of a basicdiagram (without D0 while clauses)
exists if the new structure formed may be
rewritten as a basic diagram in which the

successive actions of each section are performed

35

at the same time.

Definition 2.26. Two processes are equivalent iff their initial
states are the same and for any finite computation
in one, the computation with the same initial

state in the other has the same final state.

Two comments may now be made. First, the parallel con-
nection Of two adjacent sections of a basic diagram without DO
while clauses may not even exist. Second, if it does exist, the

new basic diagram may not yield an equivalent process.

Example 2.13. This is an example in which the parallel con-

nection between two sections does not exist.

X +— Y + a) Section 1

X €--°X - 1
Section 2
Y &F—-2

Fig 2.28

 

 

 

The new structure is:

 

Fig 2.29

36
The new structure is not a basic diagram since the first action

is illegal.

Example 2.14. This is an example Of a basic diagram for which
the new basic diagram does not yield an equivalent process. Let

P = (S,d,I) where S = i(a,b,c) ‘ a,b, and c are natural numbers}

I = (1,1,1)

and d be:

 

aé— b + c section 1

 

b £—-'a

 

 

c<--b +1 3section2

 

 

Fig 2.30

The parallel connection Of section 1 and section 2 does exist

and is d'

 

Fig 2.31

(£3,d',I) is a process with a single computation whose final state
ix; (2,2,2). (S,d,I) is a process with a single computation whose

final state is (2,2,3).

37
It is evident from the last example that care must be
taken in forming the parallel connection of two adjacent sections
Of a process. The new basic diagram generated by the parallel
connection Of two adjacent sections of a basic diagram must be
only be a basic diagram but also must generate the same final

states as the original.

Theorem 2.7. If (Rev PZUKZ) n (C10 P1U K1) 2 £6
and (R1U P1U K1)n (CZU PZU K2) = ¢
then two adjacent sections (without DO while
clauses) of a process may be connected in
parallel to yield an equivalent process.
( the subscript 1 refers to the first section,
the subscript 2 refers to the second section,

and R,C,P, and K are as before.)

Proof
In order that when section 1 references a state variable, it will
be the same in each basic diagram, the following is required:
(R111 P1) n (CZU P2

That is to say, no state variables which are referenced in section 1

UKZ) =¢

may be changed by section 2. To insure that section 2 does not
change any state variables that section 1 is saving for later
reference, the following is required:

K1 0 (CZUPZUKZ) = d
which means that no state variables which section 1 first changes

and then later references may be changed by section 2. The two

above equations imply:

(K1UR UP1) A (can) P20 K2): 15

1
By like reasoning:

(hawkau P2) n (0101311) K1): 9!

Bernstein (BERN 66) developes a Similar theorem but he
is forced to add another condition because of his use of branching.
This leads to the conclusion that structured programming lends
itself more readily to automatic detection of parallelism.

The case of DO while clauses will now be discussed.

As DO while clauses were Specifically excluded in the parallel con-
nection definition, all parallelism will be considered from the
viewpoint of detecting parallelism within the body Of a DO while
clause. If there are othr D0 while clauses within the body they
may not be used in making a parallel connection. If the last
statement of a D0 while clause modifies a state variable in the
Boolean expression it must also be excluded. (By the definition

of DO while clause, this is the only place that such a modification
may take place.)

If the DO while clause contains no indexed state vari-
ables, this analysis is adequate. If the DO while clause does
contain indexed variables, one possible solution is to expand
:it so that each of the indexed variables is indexed by an element
<Jf the index set and then apply the above techniques.' This is not
curly time consuming but is sometimes inpossible. The approach taken
iJI (LAMP 74) may be used but the results of Lamport are SO restricted

tluat they apply to few D0 while clauses.

Chapter 3

SUFFICIENT CONDITIONS FOR POSSESSION OF AN INFINITE COMPUTATION

The appendix contains the terminology needed for the use
of digraphs in this thesis. The digraph of a process P has as its
vertices SX N, where S is the state Space Of P and N is its labels.

The directed edge (p,q) will be in the digraph if and

only if f(p) = q where p and q are in S)‘N, and f is the successor

 

 

function.

Definition 3:1. The reduced digraph of a process P is the
digraph of P with all isolated vertices
removed.

Example 3.1. Consider the process P = (S,d,I) where

S = £(a,b,c)) a,b, and c are in {0,1,233

I = £(1,1,1),(1,0,2)3 , and d is:

 

a(-—b+c (mod 3)

 

D0 while b f O

 

 

 

lb‘r—'b + 1 (mod 3)

 

Fig 3.1

39

40

For this process the re uced digraph is:

(1,1,1,1)

 
   
 
 

(1,0,2,1)
(2,1,1,2)

(2,0,2,3)
(2,2,1,2)

(2,0,1,3)

Fig 3.2

The vertex (2,0,2,3) and the vertex (:,0,1,3) are final states.
Recall the convention mentioned earlier Of labeling the final
states with n + l as a level, where n is the number Of levels in
d.

In the above example, both the digraph and the reduced
digraph of the process were finite. To obtain the digraph, the other
points in the state Space are merely added. In the next example,

the reduced digraph is finite while the digraph is infinite.

IExample 3.2. Consider the process P = (S,d,I) where
S = €(a,b,c) a,b and c are natural numbers)

I is ((1,1,1), (0,0,0), (0,0,113 and d is:

41

 

DO while b (L 1

 

a (r—- b + l
c (—-— a + l

b 4i- c

 

 

 

 

 

 

Fig 3.3

The digraphs of this process will have an infinite number of

points but the reduced digraph is:

   
 
     
 

(1,1,1,1) (o,o,o,1) (0,0,1,1)
(1,1,1,4) (19091’2)
(1.0.2.3) (1,0,2,3)
((1.2,2,h)

Fig 3.4

The above example is also Of interest in that the computation
whose initial state is (0,0,0) has tie final state as the computation
whose initial state is (0,0,1). This kind Of joining Of computations
may occur at any point of a computation but from this point on both

computations are the same. That is to say, once two computations join

42
they may not branch. This means that the outdegree of each vertex

of a reduced process digraph is at most one.

Theorem 3.1. If a process P has a finite number of initial

 

states and its reduced digraph is infinite,

then P has at least one infinite computation.

2:22.:
Observe first that the outdegree Of each vertex is at most one,
by the way process is defined. Since the digraph is infinite,
at least one of the initial vertices (states) has an infinite
1. Now Since 81 has an infinite

number Of successors and the outdegree of each vertex is at most

number of successors, call it 8

one, 3 must be the first vertex in an infinite path, thus P has

1
an infinite computation.
Theorel 3.2. If a process P has no infinite computations

and its reduced digraph is infinite, then P

must have an infinite number of initial states.

Proof
This follows from the fact that the outdegree of each vertex

is at most one.

If the reduced digraph C of a process P is finite, then
the only way for P to have an infinite computation is for there to

be a cycle in G.

15
Theorem 3,3. If the reduced digraph G of a process
P is finite, then.G has a cycle iff G has a
walk of length greater than or equal to n,

where n is the number of vertices in G.

22.92.:
The only way for a walk Of length greater than n to exist is for
one of the vertices to be repeated, hence there must be a cycle.
Conversely, if G has a cycle, then the cycle need only be repeated
until a walk longer than n has been produced.
1
Corollary If a computation Of a process P is longer or
equal to the number Of vertices in the reduced
digraph Of P, then the computation is an

infinite computation.

The above theorem is the basis for an efficient algorithm
for determining if a process P with a finite reduced digraph has an
infinite computation. The prOperty Of process digraphs which makes this

possible is the outdegree Of any vertex is at most one.

Algorithm Let n be the number of vertices in a reduced
process digraph G and P = {V1, ...,vk‘be the
set Of initial vertices. (note that kérn)

Step 1 i £———‘l

Step 2 c<——-1

 

Step 2

Step 8

Theorem 3.4.

There are at most, n initial vertices.

Lu,

If vi has a successor, go to step 4, otherwise go to
step 6.

vie-successor of vi ; ce— 0 + 1.

If e is greater than or equal to n, go to step 7,
otherwise go to step 8.

:i‘r-'i + 1, if i is less than or equal to k, go to
step 2, otherwise go to step 8.

Halt, G has a cycle.

Halt, G has no cycles.

The algorithm must stop after checking 0(n2)
successors and there exist process digraphs for
which this bound is reached for arbitrarily

large n.

Proof

At worst, each will have

n-1 successors, with the exception of the last which will have n.

Therefore, the algorithm must step after checking 0(n2) successors.

Towshew that this bound is reached for arbitrarily large n, suppose

n.= 2r.

Consider the following digraph:

g r vertices

45
Clearly, the algorithm checks r2 successors and r2 is n2/4.
Since r was arbitrary, there exists a process digraph with an

arbitrarily large number of vertices for which the bound holds.

Example 3.3. This example shows how the algorithm may

be applied.

Let s = {(a,b,c)| a e{1,2,3_3 , be{1,23 .

c e£2,3}3
I = {(1,1,2) , (3.25)}
and d be:

 

 

 

 

 

DO while b = 2

 

zi<P-- b

bie———'c

 

 

 

 

Fig 3.6

The reduced digraph is:

(1.1.2.1) (3.2.3.1)
(1.2.2.2) (3.1.2.5)
(2.2.2.3)
(2.2.2.2)

Fit 3.?

Applying Algorith 1: v = (1,1,2,1) v2 = (3,2,3,1) k = 2 n = 6

 

 

 

1
i c v1 Step

1 (1.1.2.1) l

1 1 (1.1.2.1) 2

1 1 (1.1.2.1) 3

1 2 (1.2.2.2) A

1 2 (1.2.2.2) 5

1 2 (1.2.2.2) 3

1 3 (2.2.2.3) A

1 3 (2.2.2.3) 5

1 3 (2.2.2.3) 3

1 4 ' (2.2.2.2) A

1 4 (2,2,2,2) 5 (to be continued)

 

4?

 

i c vi Step continued
1 4 (2.2.2.2) 3
1 5 (2.2.2.3) 4
1 5 (2.2.2.3) 5
1 5 (2.2.2.3) 3
1 6 (2.2.2.2) A
1 6 (2.2.2.2) 5
7

 

 

 

Note that 5 successors were checked.

Definitieng3.2.

The cencep

usefulness of the alg

Let G = (V,E) be a reduced process digraph.

The condensation Of G.with reSpect to a
partition of V, is the digraph whose points

are the subsets Of the partition and whose lines
are determined by the following rule: there is
a line from point S1 to point S:j to the new
digraph iff in G there is at least one line

from a point of S1 to one Of S3, for i f 3.

If i = j and Si is finite, there is a loop

at Si iff there is a cycle in Si. If Si is
infinite, there is a leap at Si (if there is a cycle

in Si or if there is an infinite path in Si)’

t of condensation may be used to extend the

orithm.

48
Example 3.4. let S = {(a,b,c) l a,b, and c are natural
numbers)
I e. 01.1.1) , (2.2.2) . (3.3.38

and d be:

 

 

 

 

 

 

 

 

Fig 3.8

It is evident that the reduced digraph G = (V,E) of this process

is infinite. Consider the following partition of V:

S1 = L(a,b,c,n)1 c > 12 and a is even3
$2 = {(a,b,c,n) \ c 7 12 and a is Odd}
S3 = {(a,b,c,n) \ c 5. 12 and a is even}
St, = Z(a,b,c,n) \ c 12 and a is odd}

where n is in {1,23

The condensation Of G is as.follows:
31+ S
0 °

Fig 3.9

U)

49

I = {S4, 33. $2)

The initial vertices are just these vertices for which there exists
an x 6 Si such that x was an initial vertex of G.

If the algorithm is applied to the condensation Of G,
it halts in step 7. This leads to the conjecture that the process
may have an infinite computation. The following exarnple shows that

such a conclusion cannot always be made.

Exanmle 3.5. Let S = {(a,b,c) I a,b, and c are natural
numbers3

I = 81.1.1). (2.2.28 and d be:

 

DO while 0 9’: 12

 

bfi—‘b+1

 

c<——-—-c+1

 

 

 

 

Fig 3.10

Consider the following partition Of SK N:
1 - {(a,b,c,n) I c is even} ne (1,2,3;
32 - £(a,b,c,n \ c is Odd 3 n‘ e{1.2.33

S

The condensation of the reduced digraph of P is:

Fig 3.11

The algorithms halts in step 7 for the condensation but the
reduced digraph is finite and cycle free.

The last example shows that the condensation of a
reduced digraph of a process may have a cycle while the reduced
digraph is cycle free. The following theorem shows that if there is
a cycle in the reduced digraph Of a process, then any condensation

must have a cycle. (In some cases, the cycle will be Of length 1.)

Theerem_3.5. If the reduced digraph of a process has a

cycle, then so does any of its cendensations.

£2221:
Let P = (S,d,I) be a process and G be its reduced digraph.
Suppose G has a cycle: r1,r2,...rn,r1 where the ri are in SX N.
Let S1 be the partition of SXN, then for each ri there exists an
Sr. such that ri is in Sr. . Consider the walk:

1 1
Sr1’ Sr2 ’ rn r1 ’
this walk contains a cycle in the condensation Of'G.

... S ’ S

The reason that the converse Of the above theorem does
not held becomes apparent when the proof of it is attempted. Suppose
31’52”"Sn’s1 is a cycle in some condensation of a reduced process

digraph. The definition Of condensation implies that there is a

51

line between a point in S say r1 and a point in S say r2.

1 2
It also guarantees that there is a line between a point in 32

say ré and a point in S3 say r3. What it does not guarantee is
2 to ré. It would seem natural then
to say that if the strongly connected components of the reduced

that there is a path from r

process digraph are chosen as the partitions, that the reduced
digraph will have a cycle iff this condensation does. This is
quite true but it is completely useless. If any of the strongly
connected components have more than a single point then the reduced
process digraph has a cycle, otherwise the partition is the trivial
partition. The above arguments Show that it is useless to try to
find some Special class of condensatiens for which the converse

of the above theorem holds for all processes.

Definition 333. A process is said to terminate if it has

no infinite computations.

Theorem 3.6. A process P terminates if there is a finite
condensation Of the reduced digraph of P

which is cycle free.

the:

If the reduced digraph of P is finite, this follows from the
previous theorem. If the reduced digraph of P is infinite then at
least one of the Si contains an infinite number of vertices. Since
there is no lOOp at any of the Si which are infinite they do not

contain cycles or infinite paths. Since there are no cycles in the

52
condensation itself there is no way for an infinite path to exist
in the reduced digraph. This is evident from the fact that since
the infinite Si contain no infinite paths themselves, the only way
for an infinite path to be in the reduced digraph would be fer its

points to alternate between the Di. But there are only a finite

number of Si, this would cause a cycle.

Chapter 4

MEASURES OF PROCESS COST

In this chapter, the concept of measurement of the
prOperties of a process is discussed. Three measures which appear
to have some practical Significance are suggested. In Section One,
these measures are discussed at the computational level, while in
Section Two, the concepts develOped in Section One are extended to

provide a single measure for a whole process.

4.1. COMPUTATIONAL COST

Definition 4.1. The lepgth Of a computation shall be the

length of the equivalent path in the process

digraph.
Definition 4.2. The width of a computation shall be the

 

maximum number of state variables changed
between any two adjacent vertices in the
equivalent path in the process digraph.
Definition 4.3. The 3255' of a computation shall be the
number of assignments of values to state

variables during a computation.

53

54

These three measures were chosen because there was
a need for each in the develOpment of an adequate theory Of
measurement of process. The notion of length correSponds most
closely with the measure of time. The notion of width, in a
practical sense, might be needed in considering the implementation
of a parallel programming configuration as a process. Clearly,
each computation of the process must not exceed a certain width
(i.e. - the number of processors available). The concept of
work is necessary in order to have some way of measuring how
many changes in the state variable space a particular computation
makes. The following example will be used to point out the interelation

between these measures.

Example 4.1. This is an example of a process for which

the length and the work both have the same numerical value for all
computations. Let P = (S,d,I) where

i(A,B)l A and B are natural numbers}

{(1.1)3and d is

S

I

 

D0 while A‘S

[pB"B + B

I A‘-A + 1

 

 

 

 

Fig 4.1

This process has a single computation:

< (1.1).(1.2).(2.2).(2.3).(3.4).(3.8).(4.8),(4.16).(5.16)>

55

The length of the computation is 8 and its work is 8.

Example 4.2. This is an example of a process for
which the numerical value of work is larger than the numerical
value of time. It has the same state space and initial state

as the previous example but with the following basic diagram:

 

D0 while A <2 5

 

 

 

 

 

 

It has but one computation:
((1.1).(2.2).(3.4),(4.8).(3.16)> -
The length of the computation is 4 and its work is 8.

Example 4.3. This is an example of a process for which
the numerical value of length is larger than the numerical value
of work. It has the same state Space and initial states as before

but the following basic diagram:

 

DO while A

_L

ll
.3

 

 

 

 

Fig 4.3

56
It has only one computation but it happens to be an infinite one:
((1,1),(1'1)’000> .

The length of this computation is infinite but its work is O.

Examplg 4.4. This is an example of a process where the
length and the work have the same numerical value for one computation
but a different value for another. The state Space is the same as
the last example but the initial states are:

(1.1) and (1.2)

and the basic diagram is:

 

 

 

 

 

litr‘i3 [ llfi-fiS l B1‘-'3

 

 

 

l -

 

Fig 4.4

It has the computations:
C1 <(1.1),(3.1)> and
2 ((1.2).(3.3>> .

C

In the first computation, both length and work have a value of 1

while in the second, length has a value of 1 and work has a value
of 2.

The above examples suggest a relationship between the

57

three measures for a typical computation. Example 4.3. is the lone
exception and suggests that processes with null actions may be difficult

to include in such a relationship.

Observation 4.1. In a process with no null actions, the
numberical value Of length is always less than
or equal to the numerical value of work for any

computation.

Proof
If no null actions are allowed, at least one state variable must be

changed between each state of any computation.

Observation 4.2. In a process with a maximum width of n the

work of any computation is less than or equal

to n times its length.

Proof

At most, n changes are made per computation.

Observation 4.3. In a process with no null actions and no
actions whose cardinality is greater than 1,
the work and the length of each computation have

the same numerical value.

Proof
It follows from the last two theorems.
The three previous definitions of measurable quantities

give rise to some measures which are defined in terms of them.

58
Definition 4.4. The rate of a computation is its work

divided by its length.

Definition 4.5. The capacity of a computation is its length

times its width.

If both work and length are infinite, the rate is
undefined. Since length is never zero, all other Situations are

defined. The capacity of a computation is always defined.

4.2. THE COST OF A PROCESS

Attention is now turned to measures of cost of the
entire process rather than cost of a particular computation. The
first measure considered shall be that of length. As an infinite
computation would make the concept of average length meaningless,
study of process cost shall be restricted to the cost of nice

processes.

Definition 4.6. A pgpg process is a process whose reduced
digraph is finite and cycle free.
With each nice process, may be associated the following
sequence: A = (a1,a2,...) where ai is the number of computations
of length i. It follows that for each nice digraph, ai will be

zero for all but a finite number of ai.

Definition 4.7. The average length.ޣ.ef a nice process with

Definition 4.8.

59

 

sequence A = (a1,a2,...) is:
co
.2 i ai
i = 1 !_ ,
a
2:
i = 1

The variance (7'2 of the length of a nice

process with sequence A = (a1,a2,...) is:

 

es
. 2
E. (l a:l -,~gai)
1 = 1 44_ ,
a.
2:
i = 1

Both of these measures are of importance. Fer example,

suppose that a compiler is modeled by a process in which the length

of a computation is prOpertional to the compile time for a program,

then a good compiler must not only have a low average compile time

but must also have a reasonable variance. Both the average and the

variance of a process digraph suggest a certain class of diagraph

theoretic measures.

These will be discussed in the next chapter.

With each nice process, associate the following sequence

B = (b1,b2,...) where bi is the number of computations with work

equal to i. Clearly, since a nice digraph is finite and cycle free,

bi will be zero for all but a finite number of bi'

Definition 4.9.

The average work f(wof a nice process with

60

 

 

sequence B = (b1,b2,...) is:
co
2: i
i = 1
z:
i = 1
Definition 4,10 The variance 0‘ 2w of the work of a

nice process with sequence B =

(b1,b2,...) is:

as
. 2
i2 - :1 (l bi ~Awbi)

 

With each nice process, associate the following sequence

C = (c1,c2,...) where the 01 are the number of computations with
width equal to i. Since a nice digraph is finite and the width

of any computation must be finite, each ci is finite and the ci

will be zero for all but a finite number of oi.

Definition 4.11. The average An width of a nice process

 

with sequence 0 = (c1,c2,...) is:
’

 

i = l1 °i
Z:
i = l °i
2
Definition 4.12. The variance ‘rp of the width of a nice

process with sequence C = (c1,c2,...) is:

t.
. 2

 

 

61

 

 

Definition 4.13. The average rate r of a process is
Mu
M.
Definition 4.14. The average capacity c of a process is
A.“ AP .

The following example illustrates these concepts.

 

Example 4.5. Consider the process P = (S,d,I) where
S = £(a,b,c)l a,b,c are in [0,1,233

I £(1.1.1).(1.0.2)3 anddis:

 

a.<&——-b + c (mod 3)

 

DO while b # O

 

 

b‘&—-b + 1 (mod 3)

 

 

the reduced digraph is:

(1.1.1.1)

(2.1.1.2)

(2.2.1.2)

(2.0.1.3)

A (1.0.1.0.0....)
B = (1.0.1.0.0....)

c = (2.0....)

1 1..
.AH. = ———_E =
2 2

0-2 = L1-2)2 + (3-2)2

 

 

 

2
MW=L32=2
(7-5 (1-2)2 + (3-2)2
2
2
.AL = -.=
p 2 1
2 2-1-2)2 = 0
6p: '2

62

(1.0.2.1)

(290:2:3)

Fig 4.6

63

The above example suggests some relationships between the
various measures Of processes. The next few theorems point out some

relationships which Obtain to nice processes with no null actions.

Theorem 4.1. In a nice process with no null actionS,/‘¢ is

less than or equal terbflw.

Proof
. 0., as
For a nice process E ai = 2 bi
i = 1 i = 1

because in each sequence, a computation is only counted once.

In view of observations 4.1:

ia. é; E ib.
1 l

‘9 00
i = 1

for nice processes with no null actions, thus

J».— .6 we".
Theorem 4.2. In a;nice process/KW is less than or equal

to n timesJL wlere n = max {c1,c2,...3 .

Proof
n is clearly the maximum width Of the process, hence at most n

changes are made per compuatation. Since:

2”: D

i = 1 i = 1

it follows from observation 4.2 that

My] .4. n'/(’(.. ‘

Observation 4.4. 1 s r.§ n for any nice process with no null

 

actions, where n = mach1,c2,...} .
Proof
From Theorem 4.1 and Theorem 4.2 it follows that

Since A}! 0 it follows that 1 2. r5. n.

In the next chapter, these notions of measurement will
be generalized to classes of digraphs. Just as the above measures
may be used to order nice processes, the measures develOped in the

next chapter will be used to order members within a class of digraphs.

Chapter 5

A GENERAL THEORY OF DIGRAPH MEASUREMENT

In this chapter, a scheme is develOped for assigning

non-negative real numbers to digraphs. This scheme will later be

used to obtain measures of certain digraph theoretic prOperties.

5.1. A DISCUSSION OF L AND NORMS ON L

Definition 5.1.

Definition 5:3.

Definition 5.4.

Let L,be the class of all infinite sequences
of non-negative integers with only finitely
many nonzero terms. Members of L will be de-
noted by capital letters from the beginning of
the alphabet, with terms in the sequence being
indicated by properly subscripted lower case

letters. (e.g. A = (a1,a ))

2’...
Let N'be the natural numbers.

Let I_be the non—negative integers.

Let 3.be the positive reals.

65

66
Consider L and I, it is possible to define a multipli-
cation of sequences in L by integers in I.
Definition_5,5. Let A be in L and i be in I, then i§,=

(ia1,ia2,...).

Definition 5.6. Let A and B be in L, then A + B = (a1,a2,...) +
(b1,b2,...) = (a1+b1, a2+b2,...).
If iA is thought of as a type of scalar multiplication,
the system considered here is almost a module. If falls down in
two places; additive inverses in L and additive inverses in I. It
is still possible to write A-B = (a1-b1,a2-b2,...).

but there is no guarantee of its existance.

Definition 5.7. A pppm. on L is a real-valued function d
satisfying the following prOperties for all
x in I and A,B, in L:
1) d(A) = 0 if A = 0,d(A))'0 if A g 0.
2) d(xA) = xd(A).

3) d(A + B)£ d(A) + d(B).

Definition 5.8. In is the sequence whose terms im = 0 if n # m
and i = 1 if n = m.
m
Examples of norms are now given.

sza1,32,0003

0. d(A)> o if A :5 0.

Example 5.1. d(A)

1) Clearly, d(A) = o if A

67
2) Clearly, d(xA) = Max ixa1,sa2,...3 = xMax (a1,a2,...\3= xd(A).

3) d(A+B) = Max {a1 + b,],a2 + by")! Maxfa1 + Maxfb1,b2,...x
a2 + Max {b1.b2....3 ....yiuax {b1.b2....‘3 + Maxfa1.a2....3

Examplg_5‘2._ d(A) = E f(n)an where f is a function

from N into R. n = 1

1) since f(n)? 0 for all n. d(A) = o if A = o and d(A)>o if A .5 0.

on a
2) d(xA) = E f(n)xan = x E f(n)an = xd(A).
n - 1 n = 1
go a:
3) d(A + B) = Z f(n) (an + b'n) = Z f(n)an +
n = 1 n = l
a
E f(n)bn = d(A) + d(B).
n = 1

Example 5.2. is very important since it is the only example
of norm (as shown in the next theorem) for which condition three is

an equality. Such a norm shall be called a strong norm.

 

 

Theorem 5.1. The only norms for which condition 3 is an
n
equality are those of the form d(A) = :25:
n = l

f(n)an where f is a function from N into R.

Proof
Example 5.2. shows that d is a norm. Suppose d' is a norm for which

condition 3 is also an equality. If d'(I1),d'(Ia),... are known,

d'(A) can be found for any nonzero A. It is done in the following

68

manner :

Let A be any nonzero member of L.

Since there are only

finitely many nonzero terms in A, there exists a last nonzero term,

say an. Now A z a1I1 + I + a

a2 2...

n n'

I d'(A) = d'(a1l1 + a212...+ anIn)

and since condition 3 is an equality, then d'(A) = d'(a1I1) + ... +

d'(anIn). By condition 2, d'(A)

' '
a1d (11) + ...+ and (In)° The

proof is finished since d'(In) must be greater than zero in order

to satisfy condition 1.

5.2. THE IMPORTANCE OF STRONG NORMS

The importance of strong norms from a practical standpoint

is somewhat obscured by the definition of norm given.

In this section,

the same results of section one will be obtained using standard defi-

nitions.

These results represent a slight rearrangement of results

presented by Norman and Roberts (NORM 72).

Suppose f is any function from N to R and A and B are

in L; consider the metric d defined in the following manner:

a
d(A,B) = Z f(n) lbn-anl .

4 = 1

is a metric.

Lemma;§,l.

Proof

1) symmetry:

First it must be shown that d

(L,d) is a metric space.

69

m

:- f(n) ‘an - bn‘

n=l

d(B,A)

2) triangle inequality:

& so
2: f(n) \bn - an\ + Z f(n) [en - bn\
n =1

d(A,B) d(B,C)

n=l

w

= S f(n)( \bn-an\+|cn-bn\ )
:1
m I

2 Z f(n)lbn-an+cn-bn|
n=l
co

= Z f(n) lcn-axJ =d(A,C)
n=1

3) d(A,B)2 o and d(A,B) = 0 iff A = B.
The first part is evident from the definition. If A = B, then
d(A,B) = Z": f(n) ‘ an - an\ = 0. If d(A,B) = 0, then

n = l

w
E f(n) [bu-an\ = 0, hence bn an for all 11 because f(n)

n=l
is positive.

Before proving the next lemma, the notion of one

70
sequence being between two<xhers must be defined. The Kemeny -

Snell (KEME 62) definition shall be used.

Definition 5.9, Let A,B,C be in L, then B is between A and C
ifforallm,eitheraé-.b§c orazbzc. Thisshallbe
m m m m m m

denoted by [A,B,C] .

 

Lemma 5.2. If (A,B,CJ, then d(A,C) = d(A,B) + d(B,C).
Proof
do or:
d(A,B) + d(B,C) = g f(n) )bn - an) + E f(n) \cn - bn\
n = 1 n = 1
0
Z f(N) (\bn -an\+ \cn - bn‘)
n = 1

Sinceafib ficorcgbéa foreachn, (b -a)and(c -b)
n n n n n n n n n n

have the same sign for each n, hence d(A,B) + d(B,C) =

 

“’ an
E f(n) [bu - an + cn - bnl = 2 f(n) | en - an! = d(A,C)
n = l n = 1
Lemma 5.3. d(O,Im) = f(m).

Proof

It is evident from the definition of d.

lemma 5 g. d(A + 0,8 + C) = d(A,B).

71

2323;
a

d(A+C,B+C) = Z f(n)|(bn cn)-(An on)|
n = l

= 5: f(n)[(bn-an)l=d(A,B)
n = 1

Lemma 5.2. and Lemma 5.#. resemble certain axioms used
by Kemenqunell (KEME 62) for distance between preference rankings
and Lemma 5.3. insures that d(O,A) will be a strong norm.

A theorem which is analogous to theorem one is now
proved. This theorem shows that the definition of d was in a

sense, much more general than it appeared.

Theorem 5.2. For any function f from N into R, d is the only
type of metric on L which satisfied Lemma 5.2.,

Lemma 5.3., and Lemma 5.h.

3.2.9.:

It must be shown that if there is such a metric, say d', that

d' = d. First it will be shown that d'(O,sIm) = sf(m) for any
non-negative integer s. This is done by induction on s. It is
true for s = 0 because d' is a metric, which implies d'(0,0) = 0.
Now if s) 0, then LO,(s-‘l )Im’SIm] and hence by Lemma 5.2.
d'(O,sIm) = d'(O,(s-l)Im) + d'(s-l)Im,sIm). Now

by Lemma 5.4, d'((s-l)Im,sIm) = d'(O,Im) which by Lemma 5.3. is

f(m). It has now been established that d'(O,sIm) = d'(O,(s-l)Im)

72
+ f(m). Using the induction hypothesis, this becomes

d'(0,sIm) = (3-1) f(m) + f(m) hence d'(O,sIm) = sf(m)
In order to complete the proof, define Sk to be that

subset of L consisting of sequences in which only components one
It will be established that d' = d

I

through k may differ from O.
l l

by induction of k. If k = l and A,B are in Sk’ then A = A
and B = 3111' If bl a1, then B-A is in L and hence by Lemma
5.4, d'(A,B) = d"(O,B-A) = d'(0,(bl-a1)I -.- r(1)|b1-a1) hence

d. If h a , then 8-8 is in L and hence by Lemma 5.1+.

.. _ ' ___
— f(l) b1 a1 hence d d.

d' =

d'(A,B) = d'(C,B-A) = d'(0,(bl-a1)I

If bl al, the A-B is in L and hence by Lemma 5.4, d'(A,B) -
U .. ' _ = ' - = no ' 2

d (B,A) - d (O,A B) d (o,(al b1)Il) f(l) 1 al b1\ hence d d.

To complete the induction,

Therefore d = d' for all A and B is 31'

assume that d' = d for sequences in sk—l'
If A and B are is Sk define C =

It must be shown that it

holds for sequences in Sk’
(b ,b2,...,bk_l ,ak,0,...). Clearly,[n,c,13and hence by lemma 5.2,

l
d'(A,B) = d'(A,C) + d'(C,B). But d'(C,B) = f(k)‘ bk-alj since

either 8-0 or C-B is in L and d'(C,B) -.-. d'(C,B-C) = d'(0,(bk-ak)Ik)

)I o) in the

in the former case and d'(C,B) = d‘(C-B,O_)_ = d'((ak-bk k’

latter. It is now evident that an
d'(A,B) = E f(n)! bn an)

n=1

this follows by the inductive assumption and lemma 5.1+" since A

' ' ' I —.
may be wrltten as A +akaand C as B + a I where A .. (A1,...a.k_1,o...)
and B' = (b1, ...,bk_1,0,...). d' = d since the induction is now

complete.

 

73
5.}. ASSOCIATING NON-NFIEATIVE REAL NUMEERS WITH DIGRAPHS

In this section, a method of associating non-negative
extended real numbers with each digraph in a class of digraphs,
Q, is develOped. This number is assigned in such a way that
it represents a mix of certain prOperties, each of which is
represented by a sequence in L. To accomplish this, consider
an n-tuple of functions (h',...hp) from NXQ into I such the
for all G in Q and for all m in N, hi(m,G) = o for all but
finitely many m for i = l,...,n. These n functions associate

each G in Q with n sequences in L. 81:: (hl(l,G),h1(2,G),...).

 

Definitiong5.10. s = (51,32....sn) is called the seguence tuple
of G.
1 2

Suppose d = (d ,d ,...,dn) is an n-tuple of norms on L
and there is a subset D of Ln closed under sequence addition such
that there is no digraph in Q with a sequence tuple not in D. Each
digraph G in Q is associated with a non-negative extended real number
by means of a function f(S,D). This number may be used to order the

digraphs in Q. The ordering is accomplished in the natural manner.

Definition 5.11. Let G and H be in Q with sequence tuples S8 =
. m __ . n .
(S g,...,S 8) and Sh - (S h,...,S h) reSpectlvely
and let d = (d1""’dn) be an n-tuple of norms on

L, then G.‘ H iff f(Sg,d)é f(Sh,d).

7#

Theorem 5.3. If’G and H are in Q and have the same sequence

 

tuples then for all F in Q, G£F iff Hi F and

FSG iff F1: H.

Brae:
It is evident from the definitions.

The notions defined so far may be used to obtain
several partitions of Q. This is done by defining several
equivalence relations.

1) si equivalence Let G and H be in Q, then GSiH iff G

and H have the same ith sequence in their sequence tuple

2) s equivalence Let G and H be in Q, then GSH iff G

and H have the same sequence tuple.

3) f equivalence Let G and H be in Q, then GFH iff

f(81,d) = f(Sa,d) where S1 and 32 are sequence tuples for G and
H respectively, and d is an n=tuple of norms on L of the same
dimension as S1 and 32'

Observation 5.1. The common refinement of the partitions

generated by S1 equivalence is the partition

generated by S equivalence.

f—equivalence will be used to resolve a slight problem
with the ordering obtained in the previous definition. As it
stands now, 5 is not a partial ordering of Q unless f is 1-1 and

for each G in Q, the sequence tuple is unique. However, it is

75
an easy matter to show that S is a partial ordering of the
equivalence classes of f. This is evident since the reason iuwas

not a partial ordering of Q in the first place was the antisymmetric

 

prOperty.

Definition 5.12. Let P be the collection of equivalence classes
of f.

Theoreij-t. 1/: is a partial ordering of P.

 

are;

1) Clearly, if S is in P then 33 S, since any two members of S
have the same f value.

2) Let S and T be in P. If 8131‘ and T5: S, then S andTmust have
the same f value, hence S = T.

3) Let X,Y,Z be in P. x Y implies the i value shared by members
of X is less than or equal to the f value shared by the members
of Y. Y5— Z implies that the f value shared by members of Y is
less than or equal to the f value shared by members of Z. The
above statements imply the f value shared by members of X is less
than or equal to the f value shared by the members of Z, hence

xéz.

Theoremjé. (P, 5) is a lattice.

Proof

let X and Y be in P. At least one of the following must hold:

76
l)x-‘-Y or 2) st .

Suppose 1) holds, the l.u.b. (X,Y) = Y and g.l.b. (X,Y) = x.‘
Suppose 2) holds, then l.u.b. (X,Y) = x and g.l.b. (X,Y) = Y.

If both hold, then l.u.b. (X,Y) = g.l.b. (X,Y) = X = Y.

Thanrsmhfiaér. (P,£ ) has a zero if there is a digraph H in

Q such that f(Sh,d) = 0.

Proof
Clearly, if Z =(Ge Q the 1’ value of G is zero}then

for all X in P l.u.b.(X,Z) = X.

Theorem 5.7. (P,$) has an identity if there is a digraph

in Q such that f(Sh,d) = 0’.

Proof
Clearly, if I ={G in Q\the 1‘ value of G is on} for all

X in P golobo(I,X) = X.
Theorem 5.8. (P,é) is a distributive lattice.
Proof
This is evident from the fact that P may be thought of as some

subset of the extended real numbers with the natural order.

ggeorem 2.2. Suppose there are digraphs H and G in Q such

that f(Sh,d) =09 and f(Sg,d) = 0, then (9,:— )

77
is complemented iff P consists of two classes

Z and I defined as before.

22.9.93.
Clearly, if P consists of only the two classes Z and I, then
(P, é) is complemented. Suppose there are more than two classes
in P. This means that there is a class A such that the f value for
A is not 0 or 09 . For this A there must be an A; such that
g.l.b. (A,B') = Z. The only way this may happen is for A' to be

Z. But 1.u.b.(A,Z) = A not I. So (P,§-) is not complemented.

Chapter 6
APPLICATIONS OF THE GENERAL THEORY

.6.1. BALANCE IN SIGNED DIGRAPHS

In this section, the methods of the previous chapter will
be used to develOp a measure of balance in signed digraphs. The
method develOped by Norman and Roberts (NORM 72) will be shown to
be a special case of this measure.

Intuitively, any measure of balance in signed digraphs
should involve some kind of ratio between balanced semicycles and
semicycles whose sign is negative. As a consequence, the sequence

tuples will be two-tuples and the function f will be a special kind

of function.

Definition 6.1. f(S,d) is called a £3232 function if it is
equal to dl(_§l)_ or 51333) where
dp‘(sa) d1(S1)
S = (81,82) is a sequence tuple and
d = (d1,d2) is a two=tuple of norms.
For the rest of this section, only ratio functions shall

be considered. If a digraph has no semicycles, the question of

78

79

balance is not relevant. Consequently, the<1ass of signed digraphs
that can be ordered according to balance, consists of those signed

digraphs with at least one semicycle.

Definition 6.2. Let Q be the class of all signed digraphs with

at least one semicycle.

Definition 6.5. Let h], a function from NKQ into I, be defined
as follows: h1(m,G) is the number of semi-
cylces of length m + 2 whose sign is positive.

Definition 6.1+. Let h2 , a function from NxQ into I, be defined
as follows: h2(m,G) is the number of semicycles

of length M + 2 whose sign is negative.

 

Definition 6.5. Let D = L1. L—(o,o).
Lemma Fer each sequence tuple in D there is a signed

digraph in Q with that sequence tuple.

free:
Suppose (81,82) is an arbitrary sequence tuple in D. At least
one of the Si is not zero, since (0,0) is not in D. If’S1 is not
zero, procede as follows: Start with a point x. For each S11 in S1,
construct 311 distinct positive cycles of length it'2 whose first
and last point is x.

If 32 is not zero procede as follows: Start with point x. For each

80
2 . 2 2 . . . . .
s i in S , construct S i distinct peeitlve cycles of length 1+'2
whose first and last point is x.

It should be noted that the definition of L insures that a

structure so constructed will be finite.

Example 6.1. Suppose (51.82) = ((0,1,0,0...),(2,1,0,...))

then the resultant graph would be:

 

Fig 6.10

The relation between two two-tuples of norms which
induce the same order on Q is dealt with in the next theorem.

Theorem 6.1. Suppose d1 = (d01,d11) and d = (d02,d12) are two

2
two-tuples of strong norms on L which induce the
same order of Q and f is a ration function, then

there are real numbers p and q such that dol(A) =

pd02(A) for all A in L and d11(A) = qd12(A) for

all A in L.
Proof
0 0” 0
Now d l(A) = E f 1(n) an

n = 1

co
1
d1(A) - 2 £110.)...
n = l
o °° o
d2(A) - Z f2(n)a
n = 1
1 _ as
d2(A) .. Z: f12(n)a
n = l
where fol, fll, foa, £12 are functions from N into R since
dO dll, doz, d1 are all strong norms.

l’ 2
In order to prove the theorem, it will be shown that f01(n) =

pf02(n) and f11(n) = qf12(n) for all n. Suppose n is given.
For any k and t, it is a simple matter to construct a signed
digragh with sequence tuple (kIn,tIl). Also construct a digraph

H with sequence tuple (Il,Il). Now G5 H iff

 

 

 

dOl(kIn) d1(11) iff kfol(n) ' f01(l)
4 .4
l l
d 1(tIl) d 1(11) tfll(l) f11(l)
iff fol(n)
2: .1L.
- k
f°1(n)

But since (dol,dll) and (d02,d12) induce the same order on Q

it is evident that Gfi-H iff f02(n)
t

A. ....

k

 

o
f 2(l)

82

Since this happens for all t and k, it is clear that:

 

 

fOl(n) f02(n)
O O
f l(l) f 2(l)
hence f0 (n) = [f0 (l)/f0 (1)] f0 (n)
1 l 2 2 °

A similar argument shows:

f11(n) = Lf11(1)/f12(l)] £120.)

In view of this last theorem, it is evident that the order
derived fro the digraphs in Q is quite dependent on the choice of

d (do,dl). From Theorem One of the previous chapter, it is evident

a

w
that d0(A) = E g0(n) an and d1(A) = E gl(n) an where
n = l n = l

O l . . . . 0
g and g are functions from N into R. This being the case, d
and d1 may be described in terms of g0 and g1. It would seem
reasonable to choose both g0 and g1 as some kind of decreasing
functions, since intuitively it would seem that the shorter the

semicycle, the more weight it should be given in determining

balance.

The order developed in Norman and Roberts (NORM 72)

is a special case of the techniques developed here. If d0 and

d1 are identical, this order is obtained.

6.2. COST OF RETRIEVAL FROM A BINARY TREE

Palmer, Rahimi, and Robinson (PAIN) in.a paper dealing

83
with the efficiency of binary tree storage, develop a measure for
the average and variance of the number of comparisons needed to
retrieve one item from a store of n items. In this section, their
results will be shown to be related to the class of measures der-

ived in the previous chapters.

Definition 6.6. Let B be the class of all binary forests.

 

For each G in B, associate the following sequence:
A = (al,a2,...) where ai is the number of paths on length i.
As binary forests are finite, it follows that ai will be zero

for all but a finite number f ai.

 

Definition 6.2. The average length “of a binary forest with
sequence A = (a1,a2,...) is
oo
12:: i ai
i = l
w .
2:
i = l
. . . . 2 . .
Definition 6.8. The variance 0' of a binary forest with

 

sequence A = (al,a2,...) is
w

Z (1 Bi -ALai)2

 

84
Both these measures reduce to the results given by Palmer,

Rahimi, and Robinson (PALM 74) when the particular forest in ques-
tion is the forest made up on all possihb binary stores of n items.
Palmer, Rahimi, and Robinson (PALM 7A) were able to express their
results in a manner which showed that the variance approaches

7 - 2/377 2 for large n. This raises a rather interesting ques-
tion. Can techniques similar to theirs be used in other instances

of graph-theoretic measurement?
Another way in which the theory developed in the last

chapter may be applied to the results derived by Palmer, Rahini,
and Robinson (PALM 74) is to let B be the class of all binary
forests in which each tree has exactly n nodes. The theory then
provides a means of ordering the various forests according to
average length and variance. This ordering might provide help
in devising a scheme for merging representatives from the var-

ious classes.
Example 6.2. Suppose B is the class of all binary forests

in which each tree has four vertices. Suppose further that it is

known that Gl comes from the following forest:

*1 O A

Fig 6.2.

85

and that G comes from the following forest:

 

2
F2
Fig 6.3.

O.

z:
14.03) = i=1

O

2: ..

i=1 1

where A = (5,’+,O,...O) hence M(Fl) = 51(4)- 8 = 1.3

 

M(F2) = i=1 iai
f.
i=1 ai

where A = (3,l+,2,0,0,...) hence I‘MFZ) = 3 +1: + 6 = 1.7

Acould be used tomake the decision as to how a tree known to

be from F1 might be merged with a tree known to be from F2.

A more saphisticated scheme might also make use of variance.

86
6.}. A MEASURE OF TRANSITIVITY

The question of deciding how transitive a particular
finite asymmetric digraph is, is of great importance in trying
to measure the reliability of a particular judge. Until now,
no satisfactory quantitative measure has been develOped for this.
The theory of the last chapter lends itself readily to this
problem. The only restriction made upon the finite asymmetric digraphs

is that they contain at least one path of length two.

Definition 6.9. Let Q be the class of all finite asymmetric

digraphs with at least one path of length two.

Definition 6.10. If G is in Q and sgvm), then (s) is a
maximal induced weakly connected intransitive
subgraph iff it is weakly connected and in-
transitive and there is no point v in V(S)-S

such that (SUZv3> is weakly connected and

 

 

 

intransitive.
Example 6.3. Consider the following digraph:
a {w_ c
.f ; 3

Fig 6.4.

87
let S = {2,3,4} then S is the following digraph:

 

Fig 6.5.

Now <8) is clearly intransitive and weakly connected. It is
also maximal, since if [13 is added, the resulting digraph
(s U {13) is not intransitive. For all digraphs G in Q
and for all m in N, let h(m,G) be the number of maximal induced

weakly connected intransitive subgraphs having m + 2 points.

Definition 6.11. If G is in Q and s SV(G), the < s) is the
maximal induced weakly connected transitive
subgganh iff it is weakly connected and trans-
itive and there is no point v in V(G) - S
such that < S U {V} > is weakly connected

and transitive.

Example 6.1+. Consider the digraph of the previous example.

Let S = {1.2.33 then < S > is the following digraph:

 

88
Now (S) is clearly transitive and weakly connected. It is also

maximal since if {#3 is added the resulting digraph, < SU (43 > ,
is not transitive. For all graphs G in Q and for all m in N, let
h(m,G) be the number of maximal induced weakly connected transitive
subgraphs having m + 2 points.

Now let D = L); L - (0,0), there is no digraph in Q
such that its sequence pair does not belong to D. It is evident
that for each sequence pair (S,§) in D there is a digraph G in
Q such that (S,§5 is the sequence pair of G. This is proved in

the following theorems.

Theorem 6.2. Every member of L is the transitivity (intran-
itivity) sequence of some member of Q. ( S
denotes the transitivity sequence and S the

intransitivity sequence).

area:

Let S = (a1,a2,...) be the sequence in L, for each nonzero term ai
make ai copies of the transitive tournament on i + 2 points. Since
there are only finitely many nonzero terms, the resulting structure

is a digraph. S will be its transitivity sequence. Let 5': (bl’b2"'°)
be a sequence in L, for each nonzero term bi make bi cOpies of the

cycle in i + 2 points. Since there are only finitely many nonzero

terms, the resulting structure is a digraph. S will be its intra-

nsitivity sequence.

89
Corollary Each pair (3,5) in D is the sequence pair of

some digraph in Q.

Proof
Combine the constructions in the proof of Theorem 2 and note that

(0,0) is not in D.

Let f be any ratio function and d and d' two strong
norms on L Q may be ordered by its f—values. By the results in
the previous chapter, the following theorems are evident. Let

. o - ' - -
cl and (32 be 111 Q, then GlFGa 1ff f(Sl,Sl,d,d ) - f(Sa'Sa’

where (Sl’ol) and (52,52) are the sequence palrs of’Gl and 62

reSpectively. Let w be the collection of equivalence classes of

d,d')

 

F.
Theorem 6.3. (U, 4. ) is a distributive lattice.
Theorem 6.4. (w, £- ) is not complemented.

 

In view of the last chapter, it is evident that the
order derived for digraphs in Q is dependent on the choice of

d and d'. From the last chapter, it is evident that

w w

d(s) = Z d'(S) = Z
g(n)sn and g' (n)sn

n = l n = l

90
where g and g' are functions from N into R. This being the case,
d and d' may be described in terms of g and g'. It would seem
reasonable to choose both g and g' as some kind of increasing
function. Perhaps, g(m) = mp , for all m. For example, suppose
it is desirable to have the order depend more upon the transitivity
than the intransitivity of a digraph, then the following definitions

could be made:

d(A) = w 2 d'(A) = a:
:E:: n an and 42E: n an .

n = l n = l

d(s)
The function in this case would be f(S,S,d,d') = .

d'(§5
6.#. A MEASURE or SYMMETRY

Another prOperty of digraphs which might be of some

interest to a psychologist of sociologist is that of symmetry.

Example 6.5p Suppose there are 5 couples in an apartment
complex. A psychologist might ask each couple to list their friends.
The psychologist might represent their responses by the following

digraph:

 

 

Fig 6.7.

A natural question to ask would be how symmetric is the digraph?

Symmetry in this case, would indicate a friendship was mutual.

Definition 6.12. Let P be the class of all finite digraphs with

a least one edge.

Definition 6.13. If G is in P and s S V(G), then (s) is
a maximal induced weakly connected symmetric
subggaph iff it is weakly connected and sym-
metric and there is no point v in V(G) - S
such that (St/[v3 ) is weakly connected and

symmetric.

Example 6.6. Consider the following digraph:
.3

    

92
let S = (1,2,3; then (S > is the following digraph:
3

    

Fig 6.9.

Now < S) is clearly symmetric and weakly connected. It is also
maximal since if {it} is added, the resulting digraph is not
symmetric. For all digraphs G in P and for all m in N, let h(m,G)

be the number of maximal induced weakly connected symmetric subgraphs

having m + 1 points.

Definition 6.1L». If G is in P and s S. V(G) , then <s> is a
maximal induced weakly connected asymmetric
subgraph iff it is weakly connected and asym-
metric and there is no point v in V(G) - S
such that < S UZv3) is weakly connected and

asymmetric .

Definition 6.15. For all digraphs G in P and for all m in N, let
1 (m,G) be the number of maximal induced weakly

connected asymmetric subgraphs having m + 1 points.

93
Now let D = LXL - (0,0). There is no digraph in P

such that its sequence pair does not belong to D. For each se
quence pair (8,5) in D there is a digraph.G in P such that (S,S)
is the sequence pair of G. This is evident from the following

theorem:

Theorem 6.5. Every member of L is the symmetry (asymmetry)
sequence of some digraph (S denotes the sym-

metry sequence and S'is the asymmetry sequence.

£2.92:

Let S = (81.82,...) be a sequence in L, for each nonzero term

81 make Si copies of the digraph for which E(G) = V(G)X WC),

and for which lV(G)‘ = i + 1. Since there are only finitely
many nonzero terms, the resulting structure is a digraph. S will
be its symmetry sequence. Its asymmetry sequence will be 0.

Let §'= (Ei.§é,...) be a sequence in L, for each nonzero term

E; make 3; capies of a tournament having i + 1 points. Since

there are only finitely many nonzero terms, the resulting structure
is a digraph. S will be its asymmetry sequence. Its symmetry

sequence will be 0.

Corollary. Each pair (S,§) in D is the sequence pair of

 

some digraph in P.

Proof

Combine the constructions in the proof of the above theorem and note

that (0,0) is not in D.

Let f be any ratio function and d and d' be strong norms
on L. P may be ordered by its f-values. By the results in the last

chapter, the following theorems are evident. Let G1 and G2 be in

P, then Gl‘r'G2 if and only if

f(Sl,§1,d,d') = f(32,§2,d,d')

where (S,Si) and (SZSé) are the sequence pairs of G1 and G2

respectively. Let w be the collection of equivalence classes

 

of F.
Theorem 6.6. (w, 5. ) is a distributive lattice.
Theorem 6.7. (w, fl ) is not complemented.

 

In view of the theory in the last chapter, it is evident
that the order derived for the digraphs in P is very dependent on

the choice of d and d'. The theory develOped in the last chapter

implies:
as w
d(s) = Z ) d'(S) = Z
g(n s and g'(n)s
n = 1 n n = 1 n

Where g and g' are functions from N into R. This being the case,
d and d' can be dearibed in terms of g and g'. It would seem

reasonable to choose g and g' as some kind of increasing functions.

95
For example, suppose it is desirable to have the order depend

more on symmetry than asymmetry, then the following definition

could be made:

fl so
d(A) = d'(A) =
n2 a and ‘EE:| n a .

Chapter 7

SUMMARY AND FUTURE RESEARCH

7.1 SUMMARY

 

Chapter One lays the foundation for the development of
the thesis. A review of current literature shows the need for a
definition of process which is both mathematically precise and
practically significant. The need for measurement in.a process and
the relationship between this measurement and digraph theory is
also suggested.

In Chapter Two, the concept of process is formally
defined. The decomposition theory of Hartmanix and Stearns (HART 66)
is extended to process and the problem of nontrivial parallelism
is also addressed. It is shown that in the case of nontrivial
parallelism, the best results obtainable are sufficient conditions
for decomposition.

In Chapter Three, a digraph is associated with each
process. This digraph is used to obtain sufficient conditions for
possession of an infinite computation.

In Chapter Fbur, the concept of measurement of the

prOperties of a process is discussed. Three measures which appear

96

97

to have some practical significance are suggested; the notion of
length which correSponds to time, the notion of width which may be
thought of as the number of processors needed, and the notion of work
which measures how many changes are made in the state variable space.
In chapter Five, the measurement techniques of Chapter
Four are generalized to digraphs. Chapter Six shows that two
previously defined measures are special cases of the theory in
Chapter Five and develOps two new measures which may prove useful

to social scientists.

7.2. FUTURE RESEARCH

The concept of indexed variable and its relationship
to the DO while clause is an important tapic fir future research.
It is evident that the results discussed in (LAMP 7#) may be shown
to hold for processes. Hopefully, some results which are less
trivial are obtainable.

There is also a need for the study of the relationship
between DO while clauses and If clauses within a process. For

example, the basic diagram:

 

DO while B1

 

DO while B2

DO while B;

 

 

D0 while Bk
FA

Fig 7.1

 

 

 

 

 

 

98

may be replaced by the diagram:

D0 wLile B

 

 

 

 

 

 

 

1L“.

Fig 7.2

 

provided assignments to the state variables in 32’ B3, and Eh
only occur in the last action of the basic diagram A. The task
of finding similar relationships in a more complicated nesting
structure is an open question. A reasonable conjecture to make at
this point is that any nesting of DO while clauses can be replaced
by one DO while clause and an apprOpriate number of If clauses.

A concept of nesting depth of an action may be introduced. This
concept is similar to the concept of star heights. The previous
conjecture implies that if one is allowed complete freedom in

Boolean eXpressions, any process can be rewritten as an equivalent

99

process with nesting depth one. Perhaps if the use of logical
Operators in the Boolean expressions is restricted in some way,

a process which cannot be rewritten as an equivalent process with
a lower nesting depth can be exhibited for any depth n.

The concept of process is defined in this thesis is
deterministic. Although intuitively one would want a computer
to behave deterministically, it is sometimes convenient to
introduce nondeterminism. Some notation for the introduction of
nondeterminism into basic diagrams might be develOped.

Applications of the measurement theory developed in
Chapter Five are another area for future research. Almost any

binary concept may now be measured in a more sophisticated manner.

 

APPENDIX

3100
APPENDIX

As every digraph is a relation, digraphs may be

characterized in terms of relations.

Definition 1.

Definition 2.

Definition 3.

Definition #.

Definition 5.

Definition 6.

A digraph is symmetric (asymmetric)

 

if it is a symmetric (asymmetric)

relation.

A digraph is reflexive (irreflexive)
if it is a reflexive (irreflexive)
relation.

A digraph is transitive (intransitive)
if it is a transitive (intransitive)
relation.

A digraph is complete if it is a
complete relation.

A ggaph.is a symmetric irreflexive
finite digraph.

A tournament is a complete assymmetric

irreflexive finite digraph.p

In addition to the above definitions, a number of

definitions which deal with lines and vertices of a digraph are

needed.

Definition 7.

The outdegree of vertex v is the number of

lines from v.(i.e. - lines x for which f(x) - v)

Definition 8.

Definition_9.

Definition 10.

 

Definition 11.

101
The indeggee of vertex v is the number of
lines to v.(i.e. - lines x for which s(x) = v.)
A vertex u is adjacent tg_a vertex v if there
is a line x such that f(x) = u and s(x) = v.

A vertex u is adjacent from a vertex v if

 

there is a line x such that f(x) = v and s(x) = u.
A vertex is isolated if both its indegree and

outdegree are zero.

Much of digraph theory deals with the concepts of joining

and reaching.
precise.

Definition 12.

Definition 13.

Definition IS.

Definition 15.

Definition 16.

Definition 17.

Definition 18.

The following definitions make these concepts more

A semiwalk joining v1 and vn is a collection
of vertices v1,v2,...,vn together with one from
each pair of lines vlv2 or vavl, V2V3 or v3v2,
...,vh_lvh or vhvn_l.

A semipath is a semiwalk in which the points
are distinct.

A gglk,joining v and vh is a collection of

1
vertices v1,v2,....,vh together with the lines

vlva, v2v3,...,vn_lvn .

A.pg£h is a walk in which the points are distinct.

If there is a path from u to v then v is reachable

from u.

A digraph is strongly connected if any two vertices
are mutually reachable.

A digraph is unilaterally connected if for any two

Definition 19.

Definition 20.

Definition 21.

Definition 22.

Definition 23.

Definition 24.

Definition 25.

Definition 26.

102

vertices at least one is reachable from the
other.

A diggaph is weakly connected if every two
vertices are joined by a semipath.

A digraph is disconnected if it is not even
weak.

A digraph is 522399 if it has a vertex u such
that every other vertex is reachable from u.
A gyglg’(semicycle) is a path (semipath)

with the same beginning and end vertex.

A ppgg_is a rooted irreflexive finite digraph
with no semicycles.

(This definition corresponds to what computer
scientists call a tree rather than what graph
theorists call a tree.)

A binary tree is a tree in which the outdegree
of each vertex is at most two.

A labeled digraph is a digraph in which each
line has associated with it a symbol.

A gigggd_digraph is a labeled digraph in

which the symbols are and - .

Another concept that will be of importance later in

this thesis is that of subgraph of a digraph.

Definition 22L

Definition 28.

A digraph D' is a subggaph of a digraph
D if its vertices and lines are vertices and
lines of D.

Let S be some subset of the vertices of a

digraph D, then the induced subgaph S 32

103
is the subgraph of D whose vertices are S and
in which there is a line between any two points
in S iff there is a line between these points

in D.

LIST OF REFERENCES

(BAER 68)

(BERN 66)

(BING 67)

(BLUM 67)

(BRIN 7o)

(CHUR 36)

(DAHL 66)

(DIJK)68)

(GILB 72)

(GONZ 7o)

IJST 0F REFERENCES

BAER,J.L.;AND D.P.BOVET. "Compilations of
arithmetic expressions for parallel com-
putations." Proc. IFIP Congress 1968,
North-Holland, Amsterdam, The Netherlands,
340-3116.

 

BERNSTEIN,A.J. "Analysis of programs for
parallel processing." IEEE Trans. Electron.
0 ut,Ec-15,(0et.1966)} 757-762.

BINGHAM,H.W.:D.A.FISHER;AND E.W.REIGEL.
"Automatic detection of parallelism in
computer programs." TR-ECON-O2463-4,
Burroughs TR-67-4, AD 622 274,(Nov. 1967).

BLUM,M. "A machine independent theory of
the complexity of recursive functions."
JAMC, l4, (1967(,322-336.

BRINCH,HANSEN,P. "The nucleus of a
multiprogramming system." Comm. A§§_13,
4, (1970), 238-24l,250.

CHURCH,A. "An unsolvable problem of
elementary number theory." Amer.§,
Math.,58, (1936), 3A5-363.

DAHL,O.J.: AN. NYGAARD,K. "Simula,
an AIGOL-based simulation language."
Comm. A§fl_9,9, (1966), 671-678.

DIJKSTRA,E.W. "Co-Operating sequential
processes." Programming languages, F.
Genuys(Ed.),Academic Press, New York,
(1968),A3-112.

GILEERT,P.;AND w.J. CHANDLER. "Interference
between communicating parallel processes."

GOLZALEZ,M.J.;AND C.V.RAMAMORTHY.
"Recognition and representation of

104

HARA 65)

(HART 64)

(HART 65)

(HART 65b)

(HART 66)

(HORN 73)
(KEME 62)
(KNUT 66)
LAMP 74)

(13mm 66)
(LEHM 66)

105

parallel processable streams in computer
programs." Parallel Processor

System, Technologies and Applications.

L.C. Hobbs, et al (Eds.), Spartan Books,
New York, (1970), 335-374.

HARARY,F.;R.Z. NORMN;AND D. CARTWRIGHT.
Structural Models: An Introduction to the
theory of Directed Graphs,=Wiley, New York,
(1965).

MIA-“18,010; AM) ROE. SWO "COMP-
utational complexity of recursive se-
quences.: Proceedings 2; the Fifth
Annual Symposium 2;; Switching circuit
Theory and Lo 'cal Desi . Princeton,
New Jersey, (1964), 2-90.

HARMANIS.J.;AND R..E. STEARNS. "On the
computational complexity' of Algorith s . "
hm oA-mer oMath '§.9£’ ’ 117, (1965), 285-306 0

HARTMANIS.J.;P.M. LEWIS 11mm. R.E.
STEARNS. "Hierarchies of memory lim-
ited computations." IEEE Conf rence
Record 93 Switchigg Circuit Them
_a_._nd_ ical Desi , Ann Arbor, Mich-
igan, 1 5), 179-190.

HARMANIS,J.: AND R.E. STEARNS. Al..-
gebraic Structure Theory 9_f_ Sequential
Machines , Prentice-Hall , Inc . ,Engle-
wood Cliffs, New Jersey, (1966).

HORNING,J.J.; AND B. RANDEIL."Process
structuring." ACM ut Surve ,
5, no. 1(march 1973 , 5-29.

W,J.G.; AND J.L. SNELL. Mathemati-
cal Models i_r_1_ _the Social Sciences,
Chapter 2, Blaisdell, New York, (1962).

KNUTH, D. "Additional comments on a
problem in concurrent programming
control." Com. ACM 2, 5, (May 1966).

LAMPORI', L. "The parallel execution of
DO loops." Comm. EEEHlZ’ 2, (Feb. 197A).
83-93.

IEEMAN, M. "A survey of problems and
preliminary results concerning paral-
lel processors." Proc. IEEE, 54, (Dec.
1966), 1889-1901.

 

(LEVI 71)

(MANN 70)

(MCCA 6o)

(NAss 73)

(NORM 72)

(PALM 7A)

(RAMA 69)

(Russ 69)

(SALT 66)

(TURI 37)

106

LENIS,F.D. "The enumerability and in-
variance of complexity classes." J. of
Comp. and Sys, Sciences 5, 3, (June
1971), 286L303.

MANNA, Z. "Termination of programs re-
presented as interpreted graphs." Proc.
AFIPS 1970 SpringgJoint Computer Conf.,
AFIPS press, Montvale, New Jersey, 83-89.

MCCARTHY,J. "Recursive functions of
symbolic expreSsions and their comp-
utation by machine.: Commun. Assoc.
CgfiputingMachinery, 3, no. E; (1960)
l .

NASSI,I.; AND B. SHNEDERMAN. "Flowchart
techniques for structured programming.
SIGPLAN Notices, (August 1973), 12-26.

NORMAN,'...; AND F.S. ROBERTS. " A der-

ivation of a measure of relative balance

for social structures and a characterization

of extensive rationsystems." J. of Math. Psych._9
(1972 ) 0 66-91 0

PAIMER,E.M.:M. RAHIMI: AND R.w. ROBINSON.
"Efficiency of a binary comparison storage
technique." (to appear).

RAMAMOORTHY,C.V.: AND M.J. G- LALEZ.

"A survey of techniques for recognition

parallel processable streams in computer programs.
programs.: Proc. AFIPS 1969 Fall Joint

Co uter Conf., AFIPS press, Montvale, N.J.

1'15 0

RUSSELL,E.C. " Automatic program anal-
ysis.: PhD Dissertation, Dept. of
Electrical Engineerying, Univ. of Calif.
Los Angeles, Calif., 1969.

SALTZER,J.H. "Traffic control in a
multiplexed computer system" PhD
Dissertation, Massachusetts Institute
of Technology, 1966.

TURING,A.M. "0n computable numbers,

with an application to the entschei-
dungsdproblem." Proc. London Mathe-

matical Society 2, 42, (1936-37)

(TURS 68)

(VANW 69)

(VOLA 70)

107

TURSKI,W.,M. "SODA - adual activity

operating system.: Computer J. 11,

VAN NIJNGAARDEN,A.;B.J. MAILLOUX,
J .E.L.PECK; AND C.H.A.KOSTER. "Re-
port on the algorithmic language
ALGOL 68." Mathematisch Centrum.
M R 101, Amsterdam, (Oct. 1969)?

VOLANSKY,S.A. "Graph model analysis
and implementation of computational
sequences.: PhD Dissertation, Dept.
of Electrical Engineering, Univ. of
California, Los Angeles, Calif., 1970.

 

   

"'Tfll'l‘flfliflli@fllfllfilflfliflflflfiflflwflfiWTs