.....: .._...v,. , ‘ . . 1 LE , ,A: it. i ‘ ‘ ‘ 0%.? it. $822.25. irks” , ... .2 To 9.1;: ,vrfiffurtmzyhfi. , I . .. . . umfiacgfianwmauafvumfi, flquWuaiégJa. «.5 i. an. 1 . . LIBRARY mvcrsity 0' s" ”. This is to certify that the thesis entitled -ON THE COMPUTATIONAL COMPLEXITY OF CERTAIN L-RELATION OPERATORS presented by Robert H. Caron has been accepted towards fulfillment of the requirements for & degree in EE 4 Maid 3W C 0- Major professor / ,w: Co- Major Professor ‘C’lfgan State { "mt. mlflfl ‘ ABSTRACT ON THE COMPUTATIONAL COMPLEXITY OF CERTAIN L-RELATION OPERATORS BY Robert H. C aron A Z-relation is a function from a product set into the set 2 = {0, 1}. Consider, for example, the function R:XxX—>2, X arbitrary. For each ordered pair (x,y), R(x,y) = 1 if and only if ”x is in relation R to y". In terms of the Boolean disjunction (V) and conjunction (A) operators over 2, the Z—relation operators--union (+), composition ( ) and re- flexive transitive closure (*)—-can be defined: (R + S)(x,y) = R(x,y) V S(X.Y); (RS)(x,y) = VZ{R(x,z) AS(z,y)}; (R"‘)(x,y> = (2 Rk>(x,y>, kZO 1R (k 2 1) and R0 is the identity relation. where Rk = Rk- The concept of L-relation generalizes the familiar concept of 2- relation. Specifically, an L- relation is a mapping from a product set into a completely- distributive complete lattice-ordered monoid, L. The general correspondents of disjunction and conjunction over 2 are the join and meet operators of the lattice L. Additionally and without loss of generality, L is equipped with a semigroup operator which distributes over least upper bounds of L. The real closed interval J = [0, 1] is another example of a lattice—ordered monoid (Zorn) where max, min and Robert H. C aron real number product correspond to the join, meet and semigroup opera- tors, respectively. J- relations are more commonly known as fuzzy relations. This thesis studies the computational complexity of certain opera- tors in the algebra of L-relations, viz. union, dot- composition and reflexive dot-transitive closure--these being generalizations of the 2- relation operators. The model of computation employed in this study is an extended version of the ALGOL 60 reference language. The set of elementary operators in ALGOL is extended to include the join, meet and semigroup operators of an arbitrary 10m. Moreover, it is assumed that computing memory is bifurcated into main and auxiliary segments. This latter feature facilitates the consideration of L-relation Operator algorithms admitting dimensionally-large Operands, i. e. operands which, because of their size, must reside in auxiliary memory and be operated upon piecemeal. Algorithms are given which use main memory exclusively. From these it is seen that, for n x n Operands, union requires at most nz 10m operations; dot-composition requires at most 2n3 - nZ 10m operations; and reflexive dot-transitive closure requires at most 12(3) [om opera- tions. The algorithms presented are the most efficient known. The main emphasis of the thesis is toward the development of efficient algorithms for operating upon dimensionally-large L- relations. The approach taken is to decompose the L-relation operators: Each of the Operands of a given L-relation operator is partitioned into a finite set of mutually exclusive and exhaustive L- subrelations; then the corresponding partition of the resultant is expressed in terms of the resultants of compound operations, each formed exclusively by the Robert H. C aron application of L—relation operators to the L- subrelations of the operand partitions. Algorithms based upon the operator decompositions are given. In addition to being efficient with respect to the number of 10m Opera- tions required, these algorithms require only a minimal number of seeks to auxiliary memory. For pd x pd operands stored by d x d blocks in auxiliary memory, union requires at most 3pZ seeks; dot— composition requires at most 2p3 + p2 seeks; and reflexive dot-transitive closure requires at most on the order of g-p?’ seeks. Applications to the lengths-of— shortest-paths problem, single linkage hierarchical clustering and a fuzzy decision-theoretic problem are discussed. ON THE COMPUTATIONAL COMPLEXITY OF CERTAIN L-RELATION OPERATORS BY 4% Robert H." ‘ Caron A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering and Systems Science 1973 TO GIUS EPPINA A ACKNOWLEDGEMENTS I wish to thank Dr. J. Sutherland Frame who served as a co- major professor on my guidance committee. On several occasions Professor Frame offered insights and inspiration when they were sorely needed. My other co—major professor, Dr. P. David Fisher, was a constant source of encouragement during the formative stages of this research. Appreciation is extended to Dr. Joseph Adney of the Department of Mathematics and to Drs. Richard C. Dubes and Bernhard Weinberg of the Department of Computer Science for their critical review of the thesis. This thesis was supported in part by NSF Grant (31- 20 under the direction of Dr. Herman E. Koenig, Chairman of the Department of Electrical Engineering and Systems Science. For reasons extending beyond mere financial support, it can be said that Dr. Koenig is the man who made this all possible. Finally, I wish to express my sincerest appreciation to my wife for helping me to endure the emotional hardships of recent years and for sharing with me the joy of the present. TABLE OF CONTENTS Chapter Page I. INTRODUCTION . . . . . . . . . . . . . . . . 1 1. 1. Motivation . . . . . . . 1 1. Z. A Review of Fuzzy Set Mathematics . . . . . . 4 1.2.1. Algebraic Structures Relevant to Fuzzy Set Theory . . . . . . . . . . 6 1.2.2. L-Sets . . . . . . . . l4 1. 2. 3. Fundamental Properties of L— Relations . . . . . . . . . . . 16 l. 3. Thesis Contributions . . . . . . . . . . . . . 26 II. THE COMPUTATION PROBLEM . . . . . . . . . . 28 2. 1. A Model of Computation . . . . . . . . 28 2. 2. Algorithms Which Use Main Memory Exclusively . . . . . . . . . . 35 2. 3. Rationale for Operator Decompositions . . . . 42 III. RECURSIVE DECOMPOSITIONS . . . . . . . . . . . 45 3. 1. The Concept of Recursive Decomposition . . . . 45 3. 2. Decompositions of the Union and Dot- Composition Operators . . . . . . . . . 48 3. 3. Decomposition of the Reflexive Dot- Transitive Closure Operator . . . . . . . . . 50 3.3.1. A Derivation by Factorization . . . . . 51 3. 3. Z. An Alternative Derivation . . . . . . 55 3. 3. 3. Special Cases . . . . . . . . . . . . 58 IV. DECOMPOSITION- BASED ALGORITHMS . . . . . . . 64 4. 1. On the Number of [om Operations Implied by the Recursive Decompositions . . . . . . 64 4. 2. Iterative Algorithms with Adjustable Main Memory Requirements . . . . . . . . 66 4.2.1. Procedures for Union and Dot- Composition. . . . . . . . 66 4. 2. 2. An Iterative Procedure for Re- flexive Dot- Transitive Closure . . . . 69 V. APPLICATIONS . . . . . . . . . . . . . . . . . . 81 5.1. The Lengths- of-Shortest- Paths Problem . . . . 81 5. 2. The Single Linkage Hierarchical Clustering Problem . . . . . . . 83 5, 3. A Problem in Fuzzy Decision Theory . . . . . 85 Chapter Page VI. CONCLUSIONS . . . . . . . . . . . . . . . . . . .. 91 6. 1. Summary . . . . . . . . . . . . . . . . . . 91 6. 2. Future Research . . . . . . . . . . . . . . 93 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . 95 APPENDICES A. A Decomposition of the Real Matrix Inverse Operator................... 98 B. ProofofTheorem3.l ............. 101 I ' . . . . . -' -n.'.r-'. CHAPTER I IN TROD UC TION 1. 1. Motivation The report of the 1972 University of Michigan workshop on New Directions in System Science and Engineering stated, under the heading of Critical System Science Areas, that additional work is needed "to develop a fundamental understanding of the interrelationships that exist between models of uncertainty. . . and [to explore] the suitability of using these models to tackle complex mechanistic and humanistic systems. ” This thesis makes a modest contribution to this prodigious task by examining the computational complexity--and hence the computational feasibility—-of certain operators in the theory of fuzzy sets [Z- 1] . A fuzzy set may be conceptualized as a set whose boundaries are not well- defined. Whereas an ordinary set admits only belonging or not belonging, a fuzzy set can have several degrees of membership. For illustrative purposes, it suffices to use the elements of J = [0, l] , the unit interval in the real line, to describe degrees of membership in a fuzzy set. Just as an ordinary set is described by its Characteristic function, a fuzzy set is defined by its membership function. In particu- lar, if S is a fuzzy set in the universe1 X, then S is completely defined 1The term universe refers to an ordinary set on which fuzzy or ordinary sets are defined. by a membership function us:X—> J. For example, the fuzzy set A = "small" on the positive real line (R+) might have a membership function of the form “Am = [1 + = e"1/“"X'Y' (a 6R.) for each ordered pair (x,y) in R+ x R+. If the a in “B is the same as the o. in ”A’ then a/9 and 0/10 which were both regarded as "small" are also "not much different from" one another. On the other hand, 10. lo. and 100 are ”not much different from” one another, but neither can be con- sidered ”small". During the past few years, fuzzy set theory has come to be accepted by many as an alternative to probability theory for the purpose of model— ling phenomena involving uncertainty [ B-Z, C- 1, G-Z, T- 1, W-Z] . Fuzzy set theorists espouse the belief that humanistic systems--such as those studied in the areas of economics, psychology, ecology and lin- guistics-- and large-scale mechanistic systems--such as computers, nationwide air traffic control systems, urban mass transit systems and models for weather prediction, to name but a few--exhibit a kind of uncertainty which stems more from ambiguity than from randomness. The essence of this conviction is most easily grasped when one con- siders that a principal source of uncertainty in the aforementioned systems is the human language. Despite their ambiguity, words and phrases such as "small" and "not much different from” serve to define goals and constraints in complex systems; moreover, most complex systems possess communication channels which support fuzzy termi- nology exclusively. The intended role of fuzzy set theory in the model— ling of complex systems is to provide mathematical tools which facilitate the use of ambiguous information in a systematic manner. At its present stage of development, fuzzy set theory can be re- garded only as a potential aid to the investigation of real-world problems. For while it is true that the theory seems applicable to several general problems pertaining to systems of a complex genre, few real- world solutions have been produced. This applications drought is most likely attributable, at least in part, to the following: i) The fuzzy set concept is new, and the attention it has received is from individuals who are theory-oriented. Unfortunately, what is an application to a theorist may still be theory to an applied scientist. ii) The philosophy underlying the approach to problems from the fuzzy set viewpoint is not easily grasped or, for that matter, well-developed. The computational feasibility of the Operators implicit v iii in fuzzy set mathematics has not been explored, thus precluding the establishment Of conclusions as to the suitability Of fuzzy set theory for solving problems. This thesis confronts the third is sue by examining the computational complexity of the union, composition and transitive closure operators in the algebra of fuzzy relationsl. Heretofore, no investigations have been reported on this subject, although a few discussions of the most funda- mental aspects Of fuzzy relations can be found in the recent literature [G- 2, Z-3, T- l] . The work reported here will probably be most valu- able to applications of the emerging theory of fuzzy systems [Z-Z] where the concept of fuzzy relation is central. It can be anticipated that forthcoming applications of this area will require efficient computational procedures for Operating upon dimensionally-large, finite fuzzy rela- tions. It is toward the search for such procedures that this thesis is devoted. A more immediate but perhaps less significant justification for this undertaking stems from a need for more efficient computational procedures to solve a certain class of graph-theoretic problems which includes single linkage hierarchical clustering [J- 1, G-3] and the 1engths-of—shortest-paths problem [B-3, Chapter 6]. These problems, although originally posed outside the context of fuzzy set theory, can be solved using the aforementioned fuzzy relation operators. 1. 2. A Review of Fuzzy Set Mathematics The term "fuzzy set" was coined in a 1964 RAND corporation memorandum [B- 1] coauthored by R. Bellman, R. Kalaba and L. A. Zadeh. However, despite the recent emergence of the concept, the mathematical foundation of what has come to be called fuzzy set theory 1A fuzzy relation is a fuzzy set whose universe is a product set. Consider, for example, the fuzzy set "not much different from" pre— sented earlier. was fully enunciated as early as 1948 by G. Birkhoff [B-4] in his now classic treatise on lattice theory. In point of fact, fuzzy set theory is an interpretation of certain ideas in the theory of algebraic lattices and, as such, constitutes an application to real—world problems of that particular branch of abstract algebra. When Zadeh introduced the concept in the open literature [2- l] , his developments were exclusively in terms of the lattice J = [ 0, l] , the closed unit interval in the real line. Later, Goguen [G- 2] defined fuzzy sets in a more general setting using a class of lattices. His approach consisted, first, in defining what he called L-sets in terms of a general lattice L and, second, in postulating a structure for L so as to make L-sets commensurate with the fuzzy set concept as set down by Zadeh. Goguen concluded that the most useful lattice structure for embodying the fuzzy set concept is that of a completely- distributive complete lattice-ordered monoid with zero, of which the lattice I used by Zadeh is an example. Currently, it is not clear that any other than J-sets are required for applications. Be that as it may, an advantage in exposition is de- rived from consideration of L-sets in general. Because of the strong relationship between the structure of the lattice L and the structure of the set of L- sets in a given universe, most of the Operations and laws in the algebra of L-sets are directly extensible from corresponding operations and laws in the underlying algebra L. Accordingly, the properties of L-sets can be developed in an axiomatic fashion with new properties being added as more structure is imposed upon L. As men— tioned above, this is the approach followed by Goguen, and it is the one adopted here. ,-'--r.1-_n'|'.-‘.-1-"-‘ as The present section is divided into three subsections. In the first of these, the structure of a completely-distributive complete lattice- ordered monoid is developed beginning with the most elementary order structure, the partially ordered set or poset. The second subsection rationalizes the formal definition of L-set, and a proposition of Goguen is invoked to extend the structure in L to a structure in the set of L-sets. Finally, in the last subsection, the class of L-sets known as L-relations is discussed; and, in particular, the fundamental properties of certain important Operations applied to L—relations are reviewed. Several of the developments presented in the last subsection are extensions of Goguen' 3 work. 1. Z. l. Algebraic Structures Relevant to Fuzzy Set Theory An ordinary set is said to possess ”structure" when certain specified relationships exist between the elements of the set. More specifically, the structure in a non- empty set S is described by a set (a) F of operators fa each mapping a power Sn of S into S, where n(a) is a positive integer. In case n(a) equals 1 or 2, f0. is a unary or binary operator, respectively. In general, the pair (S,F) is termed an algebra; however, the set S itself is Often referred to as an algebra, it being understood that a set F of operators is associated with S. The simplest, general algebra S has an associated set F which consists of a single unary operator f:S—>S. Such a unary operator defines a dyadic relation R over S according to ny if and only if y = f(x) for each x,y in S. Therefore, a set S and an associated dyadic relation R over S constitutes a kind of elementary algebra. An important class of such elementary algebras is the class of posets. Definition 1. l. A poset P is a set Over which is de- fined a dyadic relation 5, called a partial ordering, which satisfies i) a S a (reflexivity) ii) a S b, b S a implies a = b (antisymmetry) iii) a S b, b S c implies a S c (transitivity) for each a, b, c in P. [J The class of posets includes the set 2 = {0,1}, where 0 S l, and the set 2X consisting of all ordinary subsets of the set X. If A and B are in 2X, then A S B is the usual set inclusion; i. e. , A is contained in B. Further structure may be present in a poset P as the result of the existence of bounds for subsets of P. In particular, an upper bound (ub) of a subset X of a poset P is an element a in P such that x S a for each x in X; and a least upper bound (fub) of X is an elementg in P which is an upper bound of X and such that for every upper bound a of X, a S a. The notions of lower bound (1b) and greatest lower bound (ngb) are de- fined dually; i. e. , the converse relation 2 is used in lieu of S in the above definitions. Definition 1. 2. A lattice L is a poset any two of whose elements, a and b, say, have an fub or "join", de- noted lub{a,b}, and a gfb or "meet", denoted gfb{a,b}. Furthermore, a lattice is said to be complete when each of its subsets has an fub and a glb in L. D As can be seen from the next theorem, due to Birkhoff [B-4], and the consistency principle which follows it, the join and meet may be re- garded as binary operators on the lattice. Theorem 1. 1. Any set L with a pair of binary opera— tors (V) and (A) which satisfy the following properties is a lattice; and conversely. i) aV(ch)=(aVb)Vc;aA(bAc)=(aAb)Ac ii) aVb=bVa;aAb=bAa iii) aVa:a;aAa=a iv) aV(bAa):a;aA(bVa)=a, where a, b, c in L are arbitrary. an The properties i through iv of the so-called lattice operators, (V) and (A), are termed the associative, commutative, idempotent and absorptive laws, respectively. The relationship between the lattice operators in the previous theorem and the partial ordering S over the lattice is re- vealed by the consistency principle: For each a,b in L aVb:biffaSbiffaAb:a. From this principle and the laws in Theorem 1. 1, it is easily shown that a Vb : tub{a,b} and a Ab : g£b{a,b} . Therefore, in the sequel, (V) and (A) will be referred to as the join and meet operators, respectively. In the case Of a complete lattice L, the notation Va will denote fub L‘, where L' is a subset of L. The no— a6L' tation Aa has the obvious dual connotation. a€L' Previously, it was asserted that 2. and 2X may be regarded as po- sets; it is also true that they may be regarded as complete lattices. In the case of the set 2, the join and meet operators correspond to the Boolean operations of disjunction and conjunction, respectively; while in 2X, ordinary set union and set intersection serve as the join and meet operators, respectively. In addition to the laws appearing in Theorem 1. l, the following trivial consequence of completeness will be useful in subsequent develop- ments: If L is a complete lattice, then there exist unique elements A and y in L, termed the M and greatest elements, respectively, such that for each a in L, A S a and a S y. The least and greatest elements for the complete lattice 2 are obvious. In the case of the complete lattice 2X, the empty or null set is the least set while the set X itself is the greatest set. Certain lattices allow the join operation to be carried inside the operands of the meet operation; and conversely. This property, termed the distributive law, greatly facilitates the manipulation of expressions involving both of these Operators. Such lattices have the following special designation: Definition 1. 3. A lattice L is said to be distributive in case the meet and join operators on L satisfy the dis- tributive law; i. e. , for each a,b,c in L i) aV(b Ac) : (a Vb)A(aVc) ii) a A(ch) : (a Ab) V(aAc). Moreover, a complete lattice L is said to be completely- distributive in case its meet and join Operators satisfy the law of complete distributivity; i. e. , given a subset L' of L and the element a in L, iii) aV(/\ b) = A (aVb) bEL' bEL' iv) aA( Vb) = v (aAb). b6L' bEL' D Both 2 and 2X are completely— distributive lattices. '..:I"' ".‘:_L ' r ' 'l"'“"' 3. 10 It is often necessary to augment the structure of a lattice with an additional binary operator for the purposes of weighing cumulative effects. This gives rise to the following useful lattice structures. Definition 1. 4. A multiplicative lattice L is a lattice closed under a binary operator ( - ), called the multiqolicative pperator, which distributes over the join operator of the lattice; i. e. , for each a,b,c in L i) a- (ch) : (a-b)V(a-c) ii) (aVb)'c:(a-c)V(b-c) E) A trivial consequence of i , ii and the consistency principle is that the multiplicative Operator of a multiplicative lattice is monotone nonde- creasing in both operands. Proposition 1. 1. Let L be a multiplicative lattice with multiplicative operation ( - ). Then for each a, b, c inL a S b implies DU Definition 1. 5. A lattice-ordered semigroup L is a multiplicative lattice whose multiplicative operator is associative; i. e. , for each a, b,c in L a'(b-c) : (a°b)~c A lattice-ordered monoid L is a lattice-ordered semigroup in which there exists an identity element 1 such that for each a in L 1 ° a = a : a - l , where (- ) is the multiplicative semigroup operator. Further- more, a lattice- ordered semigroup (monoid) L which contains 11 a zero element 0 such that for each a in L 0 - a = 0 = a- 0 is said to be a lattice- ordered semigroup (monoid) with zero. D Definition 1. 6. A complete lattice L which is also a lattice—ordered semigroup (monoid) under (' ) and which satisfies i) a - ( V b) = V (a ' b) b€L' bEL' ii) (Vb)'a: V (b-a) bEL' b€L' for any a in L and any subset L' of L is said to be afl- plete lattice-ordered semigroup (monoid). In case L is also distributive as a lattice, it is called a distributive complete lattice-ordered semigroup (monoid). Finally, if L is also completely-distributive as a lattice, it is called a completely-distributive complete lattice-ordered semi— group (monoid). El Throughout this subsection, the algebras 2 and 2X have served as examples of the structures presented. Each of these algebras is also a completely- distributive complete lattice-ordered monoid with zero. For in each case, the meet operator may be regarded as the multiplica- tive semigroup operator while the least and greatest elements corre- spond to the multiplicative zero and identity, respectively. Actually, any distributive lattice is a lattice- ordered semigroup; inclusion of a greatest element makes the distributive lattice a lattice- ordered monoid; 12 and inclusion of a least element makes the distributive lattice (with greatest element) a lattice-ordered semigroup (monoid) with zero. At the beginning of this section, it was asserted that J = [0, l] is a completely— distributive complete lattice- ordered monoid with zero. The join and meet operators on J are the maximum and minimum Opera- tors, respectively. In addition to satisfying the associative, commuta— tive, idempotent laws individually and the absorptive, distributive laws mutually, the max and min operators are also continuous. Clearly, every nonempty subset of J has a largest and smallest element so J is a completely distributive lattice; the real number 1 is the greatest ele- ment and the real number 0 is the least element. There are infinitely many closed, associative binary operators on J" which distribute over the max operator. Some examples1 are i) a ' b : ab (ordinary real multiplication) ab/(a+b- ab) a,b;KO ii) a - b = 0 else iii) a ‘ b : h[ h-1(a) + h-1(b)] , where h is any continu— Ous, strictly monotone decreasing function which maps [0,00) onto (0, 1]. In point of fact, the semigroup operators i and ii are special cases of iii with h(x) : e_X and h(x) = l/(l + x), respectively. It follows from the conditions imposed upon h that any semigroup operator de- fined by iii has the real number 1 as an identity. Furthermore, by defining lim a - b and lim a - b to be the real number 0, it follows that a» 0 b» O 0 is a zero for the semigroup operator (' ). le. section 6. 2 in Aczél [A- 1] . 13 Among the examples of lattice-ordered monoids given by Goguen [G— 2] is R(A), the regular subsets1 of the free monoid generated by the finite set A under concatenation. Using A together with 4) (the empty set) and A (the concatenative identity element), R(A) is defined induc— tively as follows: i) Each a€A, A and <1) are in R(A). ii) If a and [3 are in R(A) then so too are a + [3, (1(3 and (1*. Here (+) denotes set union in the ordinary sense; juxtaposition ( ) de- notes set concatenation; i. e. , 0.6 : {ablaEQ andbEB}; and (*) denotes Kleene closure; 1. e. , a = Z a , 120 0 k k-l . . where o. : A and o. = o. a, k 2 1. Although ordInary set Intersec— tion does not appear explicitly in the definition of R(A), it can be shown that R(A) is closed under this Operator. Therefore, while set union serves as a join operator for R(A), set intersection serves as a meet operator. The multiplicative semigroup operator is concatenation, which clearly distributes over union. Note, however, that R(A) is only conditionally complete since it is closed only under countable unions and intersections. The subject of regular sets will be revisited at the end of Sub- section 1. 2. 3. 1For a comprehensive treatment of regular sets and their rela— tion to automata, consult Ginzburg [G- 1] . l. 2. Z. L-Sets The concept of a fuzzy set was characterized in the introduction to this chapter as a generalization of the notion of an ordinary set. To better understand the nature of the generalization, consider that an ordinary set A in a universe X is described by a characteristic function fA2X—> 2, where 2 : {0, 1}. Given an element x in X, the membership of x in A is determined by the image of x under fA. The usual convention employed is that fA(x) : 0 in case xi_sn_ot in A; while, fA(x) : l in case x_i_s_ in A. There are but two degrees of membershipl. Now Since a crisp set is completely described by its characteristic function, it is mathematically correct to consider a crisp set in a universe X to be a function from X into 2, provided that the structure which implies cer- tain relationships between all such functions is acknowledged. That is, the set 2X of all sets in X may be regarded as the set of all functions from X into 2, together with an associated pair Of binary operators on 2X, called "set union" and ”set intersection", which satisfy certain laws. In the previous subsection, it was asserted that the structure in 2X defined by these operators is that of a completely-distributive lattice; moreover, it was also asserted that the set 2 is a completely-distribu- tive lattice under the Boolean operations of disjunction and conjunction. Soon it will be apparent that the operators in the lattice 2 bear a strong relationship to the operators in the lattice 2X; indeed, “set union" and ”set intersection" are defined by pointwise extension of disjunction and conjunction, respectively. If (U) and (0) denote the join and meet on 2X, while (V) and (A) denote the join and meet on 2, then given sets A 1Hereafter, sets with only two degrees of membership shall be termed ”crisp", and this term shall be used in lieu of "ordinary”. and B in X fAUB(x) = fA(x) V fB(x) fAflB(x) = fA(x) A fB(x) define the characteristic functions of AUB and AflB, respectively. With this view of the algebra of crisp sets in mind, it is clear that the concept of membership can be widened by increasing the poten- tial degrees of membership beyond two, i. e. , by replacing the set 2 with a set L containing more than two elements. If the resulting notion is to be truly a generalization, then the structure in L should at least be that of a completely- distributive lattice. No loss in generality occurs if L is considered to be a completely- distributive complete lattice-ordered monoid, because, as was pointed out in the previous subsection, the completely—distributive lattice 2 also possesses the monoid structure when the conjunction operation is further regarded as a multiplicative semigroup operator on 2. The nature of the generalization of crisp sets to fuzzy sets or, more particularly, to L-sets is now established. In the sequel, the following formal definition will apply. Definition 1. 7. AnL;s_et A in the crisp universe X is a function A:X«> L, where L is a completely- distributive complete lattice-ordered monoid with zero whose identity and greatest element coincide and whose least element is also the zero under the multiplicative semigroup operator. Furthermore, the set of all L-sets in X is denoted LX. CI As promised in the introduction to the present section, a proposition, due to Goguen, yields a condition whereby the structure in L can be extended to LX. 16 Proposition 1. 2. LX can be given whatever operators L has, and these operators on LX will obey any law valid in L which extends point by point. DD In consideration of this proposition, the utility of the postulational approach should now be apparent: All of the fundamental properties of L—sets are direct consequences of the structure prescribed for L in the definition of L-set. Before proceeding to a discussion of the particular class of L— sets known as L- relations, it is necessary to comment briefly on the intended role of the completeness postulate in Definition 1. 7. The reason com- pleteness is included is to make for a smoother theoretical development. The theoretical advantage of completeness is that the existence of bounds on infinite sets never need be questioned. (To appreciate this situation, consider that in real analysis sums of infinite sequences Of real numbers must always be tested for finiteness. ) On the other hand, most computer-oriented applications are of a distinctly finite character; operations are performed only on finite sets. Therefore, many of the ensuing developments in this thesis, although made under the complete- ness postulate, could well apply in finite cases without the completeness postulate. Many Of the results contained herein apply, in finite cases, to an even broader class of admissible algebras than the one specified in Definition 1. 7. 1. Z. 3. Fundamental Properties of L— Relations The principal concern in this dissertation is with the special class of fuzzy sets known as fuzzy relations or, more specifically, as L— relations. By definition, an L—relation is an L—set whose universe is II I 17 a product set of the form Ill Xk’ where each Xk is a crisp set and n > 1. In this thesis, onlylfthe case n = 2 will be considered; however, many of the results to follow may be extended, mutatis mutandis, to arbitrary n > 1. According to the notation in Definition 1. 7, the set of L-relations with universe XY is denoted by LXY. For any L—relation R in LXY, the set X shall be called the antecedent set of R; and the set Y shall be called the consequent set of R. A fini L-relation is one whose ante- cedent and consequent sets are finite. The dimensions of a finite L- relation are given by an ordered pair (na, nc) of positive integers, where na and nC are the sizes of the antecedent and consequent sets, respectively. For ease of exposition in the sequel, the antecedent and consequent sets for an L- relation with dimensions (n,m) will consist of sets of consecutive integers { 1, Z, . . . ,n} and {1, 2, . . . ,m}, respectively. Moreover, each finite L-relation with dimensions (n,m) may be thought of as an nxm matrix whose entries are elements in the lattice— ordered monoid (l om) L. Indeed, such an L—relation will often be referred to as an nxm L- relation. An L- subrelation of an L-relation is a restric- tion of the latter. That is, if R is in LXY, then for any U Q X, V g Y, the function S:UV—> L, defined according to S(u,v) : R(u, v) for each ordered pair (u,v) in UV, is an L- subrelation of R. Clearly, S is completely defined by R, U and V. Observe, too, that S itself is an L-relation but with antecedent set U and consequent set V. As with any set of L-sets, LXY possesses the algebraic structure of L. In particular, the union (+) of L- relations in LXY is defined in terms Of the join operator (V) on L. 18 Definition 1. 8. Let R and S be in LXY. Then the union of R with S, denoted R + S, is also an L-relation in LXY defined according to (R + S)(X,Y) = R(XJ) VS(X.Y) for each ordered pair (x,y) in XY. D Notice that the only condition necessary to as sure the union- compat'- Mof R with S is that they have the same antecedent and consequent sets. Owing to the completeness of L, it is possible to define the union of collections of mutually union-compatible L-relations. Thus, if C is a subset of LXY, then 2 R is an L- relation in LXY defined according to REC ( E R)(X,Y) = V R(X,Y) R€C Rec for each ordered pair (x,y) in XY. It is also possible to extend pointwise to LXY the meet operator (A) and semigroup Operator (-) on L; however, the resulting L-relation operators will not play a role in subsequent developments and so these extensions are not considered. In any case, a useful binary multiplica- tive operator can be defined in terms of the join and semigroup Operators on L. Definition 1. 9. Let R be in LXZ and s be in LZY. Then the (join) dot-composition of R with S, denoted R -_ S, is an L—relation in LXY defined according to (R;S)(x,y) : V {R(x,z) - S(z,y)} ZEZ for each ordered pair (x,y) in XY. Here (' ) is the semi- group (or possibly the meet) operator on L. [3 19 Hereafter, except when specified otherwise, the symbol .'_ will denote dot-composition. In specific instances the word ”dot" will be replaced by whatever name applies to the multiplicative semigroup operator. For example, with J- relations min- composition applies when (- ) is the min operator; whereas product- composition applies when (° ) is the usual (real number) product. As with the (+)-operator, (1.) is valid only when the L-relations being dot- composed are compatible. In particular, the L- relation R is said to be composition-compatible with the L- relation S if and only if the consequent set of R coincides with the antecedent set of S. Using the properties postulated for the (V) and (°) operators on L, several laws involving the (+) and (-_) operators become evident. Since, however, these laws are demonstrated elsewhere [Z-3, G- 2] , it will suffice to indicate the properties in L from which they obtain. In the equations and inequalities which follow, Q, R, S and T denote L—relations; moreover, in each occurrence of a union or dot-composition, the L- relations involved are presumed to be compatible in the sense of the operation performed. The three most obvious laws satisfied by (+) are associativity, commutativity and idempotency. Each of these follows immediately from its counterpart in Theorem 1. 1. R+(S+T)=(R+S)+T (1.1) R+S=S+R (1.2) R+R=R (1.3) Since (L) is not the result of a pointwise extension from a single operation on L, laws involving ('_) do not follow immediately from corresponding laws for operators on L. The associativity of (L) arises r 20 not only from the associativity of (° ) but also from the commutativity of (V) and the complete distributivity of ( ° ) over (V). These latter two properties are also responsible for (.L) being completely distributive over (+). Thus, R'_(S-.T) = (R-_S)-_T; (1.4) R'_( Z‘, S) = Z (RLS); 56C 86C ( Z R)‘_S = Z) (RI—S). (1.5) Rec Rec It will be recalled that, due to completeness, L possesses a least element A and a greatest element y; moreover, y is an identity element with respect to (' ), while A is a zero element with respect to (' ) and an identity element with respect to (V). L- relations with cor- responding properties may also be defined. Specifically, let X and Y be arbitrary crisp sets and define L-relations IX and OXY according to y if x = x' IX(X’XI) = A if x )5 x' for each ordered pair (x,x') in X2; and OXY(x,y) : A for each ordered pair (x,y) in XY. It is easy to verify that for each R in LXY IX-_R = R = RLIY; (1.6) OZXLR : OZY; R-_OYZ = OYZ; (1.7) R+OXY = R; (1.8) that is, the 1's are multiplicative identities, while the O's are multi- plicative zeros and additive identities. The partial ordering relation S over L extends to a partial order- ing relation g over LXY in the following fashion: If R and S are in LXY, E; 1:970 21 then R g S if and only if R(x,y) S S(x,y) for each ordered pair (x,y) in XY. An alternative and often more useful definition of g obtains from the consistency principle on L. In particular, RQS ifandonlyif R+S=S. Hereafter, this latter definition will be referred to as the consistency principle on LXY. Employing this consistency principle, it is easy to demonstrate that both (+) and (-_) are monotone nondecreasing in both operands. In the case of (+), 1. 1 through 1. 3 are used; while for (_-_), the result follows from 1. 5. The monotonicity of these L-relation operations constitutes the very important Lemma1.l. RgSimplies i) R+TQS+T; T+RQT+S ii) RLTCSLT; TLRQTLS. DD Corollary 1.1. RQS and QQT imply i) R+Q§S+T ii) R;QgS.-.T, DU 2 Most Of the structure in L is also present in LX . Had the con- cept of ”intersection" of L- relations been developed, it would now be apparent, as Goguen has shown, that the set of L-relations whose ante- cedent and consequent sets coincide is itself a completely—distributive complete lattice-ordered monoid having a zero which coincides with its least element. Even though the identity and greatest element Of this algebra are not the same, this structure suggests the development of 22 syntactic categories of L— relations. Such matters are not considered in this thesis; however, attention is brought to bear upon important subclasses of LX . In the class of 2-relations whose antecedent and consequent sets coincide, three important subclasses exist, viz. the reflexive, sym— metric and transitive 2- relations. Corresponding generalizations can be made within the class of L- relations whose antecedent and consequent sets coincide. But before establishing these generalizations, it is necessary to introduce the concept of a converse L- relation. Specifi- cally, to any R in LXY there corresponds an RC in LYX, called the converse of R, which is defined according to Rc(y,x) : R(x,y) for each ordered pair (y,x) in YX. Definition 1. 10. Let R be in LXZ; then R is said to be i) reflexive in case IX Q R , ii) symmetric in case R 2 RC , iii) (join) dot-transitive in case R-_R g R ; moreover, if R satisfies conditions i through iii , then R is said to be a (join) dot- equivalence. C] Of particular interest in the application of 2— relation theory is the least reflexive conjunction- transitive 2-relation containing a given 2— relation. Such a least Z—relation is obtainable from the given 2-relation by application of a unary operator known as reflexive transitive closure. Recently, the operation of reflexive transitive closure, as applied to J-relations, was introduced simultaneously and independently by Tamura et a1. [T- 1] and Zadeh [ Z-3] . A definition similar to Zadeh's, but for L- relations in general, is now provided. -- r'm'd 2.3 X2 Definition 1. 11. Let R be in L . Then the reflex- >:< ive dot-transitive closure of R, denoted R , is the L- 2 relation in LX defined according to R):< = Z} Rk kZO where R0 = IX, R1 = R and Rk = R1"1 Obviously any L-relation whose antecedent and consequent sets coincide '_R for each k2 2. D is (*)-compatible. It is easily shown that the (*) operation satisfies all the properties of a closure Operation; 1. e. , for each (*)-compatible R, i) R ; RT (extensivity) >(< >5: >:< ii) R = (R ) (idempotency) >t< >1: iii) R g S implies R Q S . (monotonicity) From Definition 1. 11, it is obvious that the (*) operation is ex- tensive. Idempotency follows from the fact that J; .1, a, 4‘ fl. 4. R '_R : R , (l. 9) which is shown below using (1) the definition of dot-composition, (2) the completeness of L, (3) the complete distributivity of (' ) over (V), (4) the generalized associative law [ B-4, pg. 117] and (5) the fact that k1 k2 k1+k ;. R = R R for integral ki 2 0 (i=1, 2). Specifically, consider the value of Ra: -_R>'< at an arbitrary ordered pair (x,y) in X2: >:< >1: kl k2 (R °—R)(x,y) = (( 2 R )H 2 R ))(x.y) klzo kZZO (1) k1 k2 = v {( E R )(x,z) -( Z R )(z,v)} z€X k 20 k 20 1 2 (2) k1 k2 = v {[ v R (x,z)] '[ V R (Z.Y)]} z€X kIZO kZZO 24 (3) k1 k2 = v v v {R (x,z) ° R (Z.v)} 26X k 20 k 20 1 2 (4) k1 k2 = v v v {R (x,z) 'R (Z.v)} k 20 kzzo zEX 1 (1) k1 k2 = V V (R '— R )(X,Y) k120 kzzo (5) k1+k : V V R (XIV) k1>0 kZZO (2) = v Rk(X.y) = (z Rk)(X.y) = (R*)(x,y). k_>.0 120 By a simple induction argument, 1. 9 implies (*) is idempotent. (In fact, this same argument shows that any reflexive (*)- compatible R which is idempotent with respect to ('_) is also its own reflexive dot- transitive closure. ) Finally, to see that the (*) operator is monotone, let R and S be in LX with R Q S. By two successive induction argu- ments employing Corollary 1. 1, it is easily shown that, for each n 2 l, n n E Rk Q 2) Sk. Now since IX (_2 Ix, it follows, also from Corollary k:l k:1 n k n k n n 1.1, that, for eachnz 0, E R Q E S . Therefore, 2 R C 2) S ; :'< >‘< k:0 k=0 I120 n20 Equations 1. 1 through 1. 9 as well as Lemma 1. 1, its corollary and the closure properties of the (*)- operator will serve as useful tools in later developments. Additionally, two more fundamental formulae involving the (*) operator will be used repeatedly in the sequel: 4, 1,. = (IX+R) (1.10) I; >.. : (R .°_R)+IX (1.11) X2 where R is in L . Equation 1. 10 results from the fact that for each n20 25 n k n k . n k 2: R = 2 2 RJ = z: (I.X + R) . k=0 k=0 j=0 k=0 Equation 1. ll follows from the associativity of (+) and the complete distributivity of ('_) over (+); i. e. , * 1 k k- R = +ER = +E(R -_R) IX k.>.1 LX kzi k-l k = +(ZR ).'.R= +(ER)-’—R IX kzl 17‘ kZO = 1X+(R*.:.R). >l< =1: >§< x2 It should be apparent that the algebra L strongly resembles the algebra of regular sets in so far as they both have operators of the same form. This resemblance is even more striking when one notices that 1. 1-1. 8, 1.10 and 1. 11 are of exactly the same form as the axioms in Salomaa's consistent and complete1 axiomatic system for regular sets [5- 1] . TO obtain Salomaa's axioms one merely substitutes crisp sets in lieu of the L-relation Operands, crisp set union in lieu of (+), set concatenation in lieu of ('—) and Kleene closure in lieu of (*). Salomaa showed that this set of axioms is not only consistent but also complete if the following rule of inference is included in the system: A 316. a = es+6 implies a = 53* In other words, he showed that any equation derived within the system (axioms plus rule of inference) is valid, and any valid equation is de- rivable within the system. On the basis of the resemblances between LX and the algebra of regular sets, one is tempted to speculate as to 1The term complete is used here in the sense of axiomatics [B-5] and should not be confused with the earlier usage. 26 the existence of a similar complete system for L-relations. This feeling is further encouraged by results in Chapter III which show that a similar, albeit not so strong, rule of inference holds in LXZ. Un- fortunately the set of axioms l. l- 1. 8, l. 10 and l. 11 say nothing about how the (-_) operator is defined. Therefore, it is impossible, using these equations exclusively, to validate the equation y a y d y a. L .H. H. y], where a 2 d and b 2 c. Despite this counterexample to completeness, the consistency of the axiom system remains. The important cons e- quence of this fact is that all of the formulae which hold for regular sets 2 have counterparts in the algebra LX . l. 3. Thesis Contributions The preceding section has established the algebraic foundations of L-relation theory. In the remainder of the thesis, these ideas are used to study the computational complexity of the L-relation operators. The principal contributions of this study may be summarized as follows: i) A model of computation is postulated which closely resembles real-world digital computation. The most significant feature Of the model is that computing memory is assumed to be bifurcated into main and auxiliary segments. This facilitates the consideration of algorithms which admit Operands dimensionally-larger than available main memory, i. e. operands which, because of their size, must reside in auxiliary memory and be Operated upon piecemeal. ii) Algorithms are given which use main memory exclusively. These algorithms represent the most efficient procedures currently available for main-memory—only computation. '3th 111:;1 mania -'- -,:‘ . 27 iii) The relationship between the algebra of L- relations and the algebra of regular sets is exploited to reveal some "new" properties satisfied by the L- relation operators. These properties are used to recursively decompose union, dot-composition and reflexive dot-transi- tive closure. iv) Iterative decompositions are obtained from the recursive decompositions, and algorithms based upon the former are created. These algorithms are applicable to L- relations dimensionally-larger than main memory and, in essence, are generalizations of the algorithms which use main memory exclusively. CHAPTER II THE COMPUTATION PROBLEM This chapter commences a systematic investigation toward as- certaining the difficulty of performing the union, dot-composition and reflexive dot-transitive closure operations in a finite- size, discrete- time, sequential computing medium. To facilitate this investigation a model of computation is postulated which allows each of the afore- mentioned operations to be translated into a set of surrogate-computer instructions called an algorithm. A significant feature of this model is that it takes into account the storage dichotomy extant in most modern computer installations, i. e. the bifurcation of storage into a main memory and auxiliary memory. Following the presentation of the model, Several L-relation operator algorithms are given. These algorithms are of the type which use main memory exclusively and, hence, are applicable only in situations where the Operands, realized as matrices, are Of sufficiently low dimension to fit in available main memory. The chapter concludes by outlining an approach to the development of efficient L- relation Operator algorithms which admit operands dimensionally- larger than available main memory. 2. 1. A Model of Computation For the issue of computational complexity to be rigorously pur- sued, it is necessary to postulate a model of computation. In its primary capacity, the model provides a medium in which metaphysical 28 29 embodiments of a mathematical operation may be synthesized. Implicit in the structure of this medium is a measure of computational com- plexity, i. e. the "effort" required to perform an operation via an em- bodiment of that operation. Such a measure provides the means to compare distinct embodiments of the same operation, thus permitting statements concerning relative efficiency. Without the point of reference afforded by a model of computation, statements of this kind tend to be ambiguous. The form which a model of computation should take in a given set of circumstances is dictated by two considerations: (i) the motivation for seeking an embodiment of the operations in question and (ii) the level of conceptualization from which the operations themselves should be viewed. In this thesis, the emphasis is toward gaining insight into the difficulty of performing L- relation operations on digital computing machines programmable via high-level languages. This motive sug- gests that the model must possess a semblance of the organization of a general-purpose digital computer and the operational character of a high-level programming language. The second consideration, viz. the level of conceptualization, is determined by the specificity of the opera- tions considered. Here, each of the L- relation operators has a fixed form relative to the join, meet and multiplicative semigroup operators of the underlying lattice- ordered monoid (form) L. Yet, despite the Specificity Of form, a substantial degree of generality prevails, con- sidering that the L- relation operators can be defined for any set L Satisfying the rather non-restrictive structure specified by Definition 1. 7. It seems appropriate, therefore, to postulate a model sufficiently general so as to warrant the creation of embodiments for any admissible I ' ' ' ' 'l ‘ . . I 03.7.. I" 'l'] llii‘b".\j " ' ‘. ' ' ' i - I. ; - - 30 L. This implies a level of conceptualization which regards the tom operators as atomic (irreducible). In accordance with the considerations set forth above, a model of computation has been postulated. This model, hereafter called MALGOL, is an extended version of the ALGOL 60 programming lan— guagel. Specifically, MALGOL is defined to be the ALGOL 60 refer- ence language taken in crisp union with a list of amendments to be given subsequently. The ALGOL 60 language was chosen as the basis for MALGOL because it is internationally accepted as a language for expressing algorithms and because it closely represents a language- system containing a hierarchy of high-level programming languages. For convenience and in the interest of clarity, the ALGOL 60 syntax will be redefined and augmented, in the amendments below, through the use of the metalinguistic formulae which appear in the ALGOL 60 report. The following quotation from that report will be sufficient to interpret these formulae: ”Sequences of characters enclosed in the brackets < > represent metalinguistic variables whose values are se- quences Of symbols. The marks ::= and | (the latter with the meaning of or) are metalinguistic connectives. Any mark in a formula which is not a variable or a connective, denotes itself (or the class of marks which are similar to it). Juxtaposition of marks and/or variables in a formula signifies juxtaposition of the sequences denoted. ” In stating an amendment references are made, whenever possible, to the section in the ALGOL 60 report to which the amendment pertains. 1H. Bottenbruch provides an excellent primer [B-6] dealing with the structure and use of this language. The authoritative description of the ALGOL 60 reference language can be found in the ALGOL 60 report [N- 1] . 31 Amendments to ALGOL 60: i) All independent basic symbols appearing in boldface font through- out the ALGOL 60 reference language will appear in underscored plain font throughout MALGOL. ii) In section 2. 3 (of the ALGOL 60 report), redefine zz=]<1 om operator> where <1 om operator>::= V] A] ‘ To avoid confusion between 10m Operators and logical operators, the latter are redefined according to ::= E] D ]o_r]a£1]—1 where substitution of this definition is understood throughout the reference language description. Also, redefine =z=< ALGOL 6O declarator>l10_rn_|r_ngl auxiliary iii) In section 2. 5, redefine zz=] <1 om number> where <1 om number>::= any member of the 10m L, it being under- stood that 1om numbers are of type 1%. iv) Since MALGOL uses 10m numbers and 10m variables, provisions must be made for 10m expressions. In section 3, redefine ::= l<1 om expression> where <1 om expression>::= (simple 10m expression>] else<1om expression> ::= <1om term>] <1 om term> <1 om term>::= <1 om factor>| <1 om term><1 om factor) ::= V V) vi) 32 <1 om factor>::= <1 om number>] <1 om variable> ::= A I ‘ Furthermore, it is assumed that all MALGOL expressions are evaluated exactly. In section 4. 2, redefine ::= l <1eft part list><1 om expres sion> where <1eft part list>::= <1eft part>] <1eft part list> <1eft part>::= <1 om variable>:= Most modern computer installations possess two distinct types of storage media: (a) a finite-size, random- access main memory which allows the contents of its storage locations to be used in expressions involving Operators and (b) a potentially unlimited- size auxiliary memory which provides additional storage but sub- ject to the constraint that values resident in auxiliary memory must first be assigned to variables in main memory before such values may take part in an expression involving operators. MALGOL, unlike ALGOL 60, takes into account the division of storage by allowing variables and arrays to be declared resident in either main or auxiliary memory. For this purpose, define ::= m] auxiliary I Then, in sections 5. 1 and 5. 2, respectively, redefine ::= ::= array] array Communication between main and auxiliary memory is achieved via assignment statements; but no direct communication is allowed between parts of auxiliary memory. 33 The term algorithm shall hereafter apply to any finite, sequential list of MALGOL statements which (i) satisfies the syntax, semantics and restrictions of MALGOL and (ii) can be executed in a finite period of time. The measure of computational complexity implied by MALGOL is the amount of time required to execute a given algorithm. This de- pends upon the amount of time required to execute each statement in the algorithm and the number of times each statement is encountered. In actual computing, the amount of time required to execute cer- tain types of statements is well in excess of the time requirements of all others. It is, therefore, a good approximation, as well as conve- nient, to ignore all but those that are temporally-dominant. In MALGOL, the only statements which need be regarded as temporally-dominant are (i) statements involving an 10m expression containing operators and (ii) assignment statements which contain a variable declared resi- dent in auxiliary memory. Type i statements are dominant because, as a rule, the embodiment of an atomic operator is more complex and hence more time-consuming than simple reallocations and compari- sons in main memory; and 10m Operations, it may be expected, re- quire several more machine instructions than are necessary to perform arithmetic or Boolean operations. Type ii statements are dominant due to the time required to find a storage location in auxiliary memory. Specifically, whenever a value is to be retrieved-from or stored-in auxiliary memory, a search must be conducted for the storage location assigned to the value. This usually involves a mechanical process in which a magnetic medium is aligned with a read/write head. As such, the process is very time-consuming; and indeed, for modern installations, 34 the seek- time, hereafter denoted by 0‘, is between 20 and 110 milliseconds 1. The complexity of an expression appearing in a type i statement is the number of 10m operations performed in that expression. The complexity of a type i statement is the sum of the complexities of the expressions appearing in that statement. Fortunately, it is not neces- sary to expend 0- units of time on each occasion that a type ii statement is encountered. This is because, to an approximation, values in aux- iliary memory are stored in a linear sequence of locations. Once a particular location p is found, any reasonable-size continuous subse- quence of locations beginning with p may be read or written- to in a time which is negligible compared to 0'. For this reason, the complexity due to type ii statements is measured by the product of 0' with the number of seeks which occur during the execution of the algorithm. Given, 3 priori, the variable address map of auxiliary memory, the complexity due to type ii statements is easily ascertained. In summary, the complexity of an algorithm A is given by the formula complexity (A) = Z [kn(k)] + (Tm k2 l where n(k) = the number times that a type i statement with complexity k is encountered in the execution of A m = the number of auxiliary memory seeks performed in the execution of A (r = seek-time. 1To appreciate the relative cost of having to perform a seek, consider that the cycle-time of a modern computer is on the order of one microsecond. ':--.::- - - - ._ I" - -. :'- .' :1.) b1 - . . '. ' . innin'} 35 2. 2. Aljorithms Which Use Main Memory Exclusively Several L-relation operator algorithms are given below, each in the form of a MALGOL procedure. The operation performed in each case is described by the first comment after the procedure heading. Use Of an array identifier in a comment refers to the contents of the array, unless specified otherwise. For convenience, it is assumed that all Operands, and hence all resultants, are n x n, where n is an integer variable. The most straightforward way of creating an L-relation operator algorithm is to directly embody the mathematical definition of the opera- tor. This approach results in efficient algorithms for union (+) and dot-composition (_L). Algorithm 2. l. procedure union(R,S, Q,n); value 11; integer n; 10m main array R,S,Q[ l:n,1:n]; comment A call to union results in Q = R + S; begin inte er i,j; for j:= 1 step 1 until mg for i:= 1 ste 1 until 11$! J: 611111;: R 11.1] VS[i:j]; end union This very simple procedure requires 3n2 10m words of main memory. Of course, if either R or S may be destroyed then the resultant union may be returned in the expendable array and only 2nZ 10m words of main memory are required. Statement J involves one 10m operation and is encountered n2 times. Therefore, the complexity of procedure . . 2 union 15 n . Algorithm 2. 2. procedure comp(R,S,Q, n); value n; integer n; 10m main array R,S,Q[1:n, lzn]; 36 comment A call to comp results in Q = R‘— S; begin integer i,j,k; 10m P; 10m main array A[l:n]; for j:= 1 step 1 until 11% be in f_ori:=ls stepluntilndg bem Dzm:P:R[i,1]-S[1,j]; i__fn=l_g22dump; £_rk:= 25tepluntilndo JD: P:= PPVR[i,Tk s[k,TJ'; dump=d Ai:=[] fir i:=-:1 ste 1 until n £12 ,j:=] A[il; end end comp This procedure requires 3n2 + n 10m words of main memory. As with procedure union, the main memory requirement can be lowered if either R or S is expendable. In such cases, only 2n2 + n 10m words of main memory are required. Statement D, involving one 10m operation, is encountered in2 times; and statement JD, involving two 10m operations, is encountered n2(n — 1) times. Therefore, the complexity of procedure comp is 2n3 — n2. In the sequel it will be useful to have a procedure which dot- composes a pair of L- relations and simultaneously forms the union of the resultant with another L-relation. Algorithm 2. 3. procedure compunion(R,S,Q,n); value 11; integer n; 10m main array R,S,Q[l:n, lzn]; comment A call to compunion results in Q' : Q + R'_S, where Q is the contents of array Q just prior to the call and Q' is the contents of array Q upon completion of the call; 37 beginin mte er i ,j,k; 10m P; f_orj:=lstep1untiln_o_ f_o; i:= ls tep 1 until nfi begin :P:= RIi,1]~s[1,j]; 2n = 1522 J: for k:= 2 steep 1 until 11 do — P:= Pv R][iv 'k'P']_[k,T- J: Q[i,j]:= Q[1 end 3251. compu—rTi—On Procedure compunion requires approximately 3n2 10m words of main memory and has a complexity of 2n3. Although the creation of algorithms for union and dot-composition is straightforward, the same is not true for reflexive dot-transitive closure. From Definition 1. 11 it appears that a countably- infinite number of (+) and (3.) Operations are necessary to perform (*). For- tunately, in the case of finite L- relations only a finite number of opera- tions are needed. This fact for the special case of J- relations and min-composition has been demonstrated by Tamura et a1. [T- l] , Zadeh [Z-3] and Bellman and Zadeh [B-2] . The most lucid treatment can be found in the latter reference where a lemma [page B- 159] indi- cating the precise nature of the simplification is stated and proven. By making a more general interpretation of the operations involved, this lemma can be restated for L-relations and dot-composition. Lemma 2. l. . X2 LetRbe 1nL whereX={l,2,...,n}, nzlarbi- trary. Let Rj denote the jth power Of R under dot- composi- tion, jz l; and let R0 = I . Then for all integral k 2 n, x k . n—l ERJ = ZRj. 1:0 i=0 DE} 38 According to Lemma 2. 1, if R is finite and with dimensions (11. n), * n-l R = E Rk (2.1) k=0 * Using 2. l and 1.10, R may be written as * n-l k R = Z(I+R) . (2.2) k=0 By by Lemma 1. l, IQI+R implies I+RQ(I+R)2; so by successive iteration 2 l IQI+RQ (1+R) g... ; (I+R)kg... g(I+R)n' . Therefore, 2. 2 implies that R* = (I +R)n‘1 Recalling l. 9, it follows that R]< can be obtained by repeated squaring of (I + R) until the exponent equals or exceeds n- l; i. e., at most [log2(n- 1)] squarings are required, where [a] is the least integer exceeding real number a. An algorithm based upon this idea and which uses procedure comp to perform the squarings requires approximately 2n2 10m words of main memory (assuming R is expendible) and has a complexity of (Zn3 - n2)]log2(n-1)]. During the course of this research an effort was made to find a (>3) operator algorithm more efficient than the one just described. This search culminated with the discovery of an algorithm which was later found to be only a slight generalization of one due to Floyd [F- 2] . Floyd's Algorithm, which solves the shortest path probleml, is based 1In Chapter V it is shown that the shortest path problem can be solved using the dual of join dot-transitive closure. -. ..'.' .,r'. 4.1 39 upon a method used by Warshall [W- l] to compute the conjunction- transitive closure of a 2-relation. More recently, Robert and Ferland [R- 1] generalized Warshall's method to matrices over a Q-semiringz; however their algorithm, too, is only a slight general- ization of Floyd's. Algorithm 2. 4. procedure transclosurel(R, S, n); value 11; integer n; 10m main array R ,:S[1 n, l:n]; comment A call to transclosurel results in S = R>‘<; begin inte er i,j,k; _f_or_ m IOI II“: 1']:— - Y e_lse S[i jl== R[i.j]: step 1 Suntil n do— 1 . Ph 0 *1 II n ,_., nu r'a‘lmrr 0‘. IE. IH‘I 1‘30 H if i - -j or i - to advancei; JD: Hid] ———[111V—£li,—kl S[k J advancei: end advancej: end en_d trans closurel The basis for Algorithm 2. 4 is best explained in graph-theoretic terms. Consider that an n x n L- relation R can be realized by a di— graph G(R) with n nodes and in which R(i,j), 1 S i,j S n, represents the strength of the link from node i to node j. A chain from node i to node j having 1 Z 2 links is a sequence of link strengths of the form C(iyj;fl) = {R(lril)’R-(11:12),°-°:R(i1_l:j)}‘ ZQ-semirings are algebras very similar to, albeit having less structure than, the lattice— ordered monoids used to define L-sets. M. Yoeli [Y-Z] conceived of Q-semirings as a means to generalize the theory of finite 2- relations. 40 The strength of c(i,j; 1) is defined as the dot-product of its link strengths taken in order; 1. e. , strength [c(i,j;1)] = R(i,il) ' R(i1,i2) ' . . . ' R(i1_ 1,j) By Definition 1. 9, it is evident that, for 1 Z 2 and i ;5 j, (R£)(i,j) is the strength of the strongest chain from i to j having 1 links. Correspond— ingly, (R*)(i,j) is the strength of the strongest chain (having any number of links) from i to j (#i). From this viewpoint, it can be verified by induction that upon completion of the pth iteration1 (lSpSn)ofAl- gorithrn 2. 4, S(i,j) is the strength of the strongest i to j chain in G(R) which only traverses intermediate nodes from the set {1, 2, . . . ,p}. Obviously, S = R]: upon completion of the nth iteration. The main memory requirement of procedure transclosurel is approximately 2nZ 10m words. This can be reduced to n2 in case R is expendable. Statement JD involves two 10m Operations and is encountered 6(I31) times. So the complexity of transclosurel is 12(3), a significant improvement over the previously described algorithm based upon re- peated squaring. If no further assumptions are made concerning the 10m L,then Algorithm 2. 4 is the most efficient of known (*) operator algorithms which use main memory exclusively. However, if it can be assumed that the partial ordering 5 over L is total, i. e. if for each a,b in L either a S b or b S a, then a still more efficient algorithm exists. The algorithm which follows is adapted from a shortest path algorithm of Yen [Y- 1] based upon Dijkstra's Principle [D- 1] for finding the lengths Of all shortest paths from a fixed node in a digraph. 1An execution of block I in Algorithm 2. 4 is considered to be one iteration of that algorithm. 41 Algorithm 2. 5. procedure transclosure2(R, S ,n); v__a__lue n;1nteger n; 1_o__m m_a_in array R, S[l: n, 1: Mn]; :1: comment A call to transclosureZ results in S = R ; comment This procedure is applicable only when the partial ordering over 10m L is total; begin integer h ,,i,j,k 1 's is; 1_o_m max; integer main array H[1:n]; 10m main array Ffl: -n]; ifn=lt thenEgipSh, 1]:=y; _g_o_t_oFe__nd; forh:1=1_st_epl_u3_tLln$ I_= REEL _f_or i: =1§£gplun_tilnd_o Est-1.12 H[i]:=i; if i — -h>\t__hen F[i]: = y _e__lse Hi]: ; end 1::h; k": H:[1]=1; H[1].— next: max:=A; Ei:=2 stepluntilk_d_o T: begin 1' =F[j 1 v FU] RU j] max:= max V F j , 1fmax:F[j]t_h_enbeginjs:=j; is: =i e__n_d end )2 — _js; 1-1[is]:: H[;k] k:= k-l; ifk> lg__t__onext; loadrow: f_or j:= 1 step 1 u__ntil 11 do S[h, j]: — Fj[ ]; en end transclosureZ During the pth iteration1 of Algorithm 2. 5, the strengths of the strongest chains in G(R) from fixed node h = p to all other nodes are computed. These strengths are stored in 10m array F. Once all strengths of strongest chains from p are known, the contents of F are loaded into the pth row of 10m array S (cf. statement loadrow). In other words, during the pth iteration the pth row of R]: is computed. This computation is based upon Dijkstra's Principle which assigns to F(j) a lAn execution of block I in Algorithm 2. 5 is considered to be one iteration of that algorithm. "ifi -. .— w -u 139': 42 tentative strongest p- to-j—chain strength during each execution of the block T. Now observe that the initial value of integer variable k is 11. Just after the n - k + l encounter with statement next (during the pth iteration), the j‘s referred to are the node numbers stored in the 2 through k positions of integer array H; these are the nodes which are tentatively labeled, 1. e. nodes whose corresponding contents in F are tentative. All other nodes, including p = H(1), have been permanently labeled during the previous n - k encounters with statement next. Upon exiting from the block T, js denotes the node most recently labeled permanent. Therefore, the node in position k of H is moved into js's position, and k is decremented by one. At this stage, if any tentatively labeled nodes remain, statement next is revisited. By consideration of block T and the fact that integer variable 1 always has the value of a permanently labeled node, it is evident that F(j), j tentatively labeled, is the strength of a chain from p to j in which all but the terminal node are permanently labeled. It follows that the node js such that F(jS) = VJ-FU) must qualify as a permanently labeled node. Note that the existence of such a js depends upon 10m L being totally orderedl The procedure transclosure2 requires approximately 2n2 + n 10m words and n integer words of main memory. Note that this requirement cannot be reduced even if R is expendable. Block T is executed (121) times during each of n iterations. So the complexity of transclosure2 is 3n(:)‘ This is a 25% improvement over the more general transclosurel. 2. 3. Rationale for Operator Decompositions Because the algorithms presented above use main memory ex— clusively, they are not applicable to situations where the Operands are "o .161; Hui-:1 'l'I-ii“ '2'--':.=.:.- 43 dimensionally- larger than available main memory. It is possible, however, to modify each of these algorithms by: (i) declaring operands and resultant to be resident in auxiliary memory, (ii) declaring smaller 10m main arrays corresponding to the largest L- subrelations operated upon at any intermediate stage and (iii) inserting assignment statements appropriately to communicate these L- subrelations between main and auxiliary memory. Since the predecessor algorithms operate on rows and/or columns at intermediate stages, the modified algorithms have greatly increased spatial bounds; but for the same reason, these modi- fied algorithms tend to be inefficient with regard to the utilization of main memory. This is because the amount of main memory that the modified algorithms use is dependent upon the size of a row or column in the operand/resultant matrices and cannot be adjusted to the main memory that is actually available. As a consequence the number of 10m operations that occur between successive seeks is less than what could be performed had more Of main memory been utilized. Corre- spondingly, the number of seeks required is greater. There is no way to dispel the "curse of dimensionality” manifest in the L-relation operators. If dimensionally-large problems are to be considered, the finite main memory Of a real—world computer must always be compromised with the temporally-expensive seeks to auxiliary memory. There is, notwithstanding, the recourse to develop algorithms which make maximal use of available main memory, with the hope, at least, of reducing the number of seeks required. One approach to the development of this type of algorithm necessitates the availability L—relation operator decompositions. Briefly, each of the Operands of a given L— relation operator is partitioned into a finite set of L- subrelations; 44 then the corresponding partition of the resultant is expressed in terms of the resultants of compound operations, each formed exclusively by the application of L— relation operators to the L- subrelations of the operand partitions. The argument ventured here is that such decom- positions will lead to algorithms whose 10m main arrays can be adjusted to maximally utilize available main memory. CHAPTER III REC URS IV E DEC OMPOSITIONS This chapter introduces the concept of recursive decomposition as it relates to L- relation operators. Decompositions based upon this con— cept are derived for union, dot-composition and reflexive dot- transitive closure. All of the results Obtained here are applicable to L-relations in general. 3. l. The Concept of Recursive Decomposition Certain notions fundamental to the recursive decomposition con— cept need to be made explicit. One such notion concerns the partitioning of an L-relation. Let R be in LXY; and let n,m be arbitrary positive integers. For 1 S i S n and l _<_ j .<_ m, let R.lj denote the L— subrelation of R with universe Xin. {Rij} is said to be an n x m partition of R if the universes corresponding to elements in this set are mutually ex— clusive and collectively exhaustive; i. e. for 11 yé iZ and/or j1 f jZ (1 5 11,12 5 n, ls jl,jZ s m) x. Y. fix. Y. = 4., 1111 1232 while simultaneously XiY. =XY. ljl J WC: CB An 11 x m partition {Rij} can be thought of as an n x m matrix whose i - j entry is the function R... This form is particularly useful when 1] 45 46 R is finite; for then, {Rij} can be realized as a partitioned permutation of the matrix realization of R, where Rij is the i - j block (submatrix) of the partitioned matrix. Also required is an explicit characterization of compound opera- tors formed exclusively from the fundamental L-relation operators. To this end, consider that a p- ary L-relation operator F is simply a function which assigns an L-relation, F(Rl’ . . . , RP), from the range of F to each p-tuple of L-relations, (R1, . . . ,RP), in the domain of F; i. e. (R ..,Rp) —F-> F(R1,...,R). 1" p Let G be a p- ary L- relation operator with domain DG’ and let H be a q- ary L-relation operator with domain DH' Then, define DG+H = {(x,y) e DGDHI G(x) is (+)-compatible with H(y)} ; DG'_H = {(x,y) 6 DGDHIG(x) is (L)-compatible with H(y)} ; D ,< = { (x) e DGIG(x) is (*)-compatible} G' If DG+H is nonempty, let G + H denote the L- relation operator defined by [G + H](x,y) = G(x) + H(y) for each ordered pair (x,y) in DG+H' Similarly, if DGLH is nonempty, let G L H denote the L-relation operator defined by [G L H](x,y) = G(X) L H(y) for each ordered pair (x,y) in DG'_H° Finally, if DG* is nonempty, let G»< denote the L—relation operator defined by >k :1: [G ](X) = [G(x)] for each x in D ,,. Now consider the class Of regular L- relation G operators which is defined inductively as follows: 47 i) L- relation operators (+), (i_), (*) and the identity opera- tor, (i), are regular. ii) If G and H are regular then so too are G + H, G '_ H and (1*. Evidently, compound operators formed exclusively from elements in the set {(+), (n), (*)} can be characterized as regular L-relation operators. Using the terminology developed above, the following definitions give precise meaning to the recursive decomposition concept: Definition 3. 1. Let the L-relation R be ($)-compat- ible with the L- relation S. 1 Furthermore let {Tfij} denote any 2 x 2 partition of R s s. The set{F.1jI1$ i,j s 2} of octonary Operators is said to constitute a recursive de- composition of $ provided that, for l S i,j S 2, Fij is regular; and Fij(Rll’R12’R21’RZZ’SII’SIZ’SZl’SZZ) : 1Tij ' where {Rij} and {8”} are suitable2 2 x 2 partitions of R and S, respectively. El Definition 3. 2. Let R be a (*)-compatible L-relation, and let {Irij} denote any 2 x 2 partition of R*. The set {Fij II S i,j s 2} of quaternary operators is said to con- stitute a recursive decomposition of (*) provided that, for l S i,j S 2, Fij is regular; and 1Here, ($) is used to denote either the union or dot—composition operation. 2A partition is suitable if its constituent L-subrelations are com- patible with the Operator Fij’ l s i,j S 2. 48 F..(R R i; 11’R12’R21’ 22) : Trij ' where {Rij} is a suitable 2 x 2 partition of R. u The decompositions described in the preceding definitions are recursive owing to the demand that the Fij be regular. Once decompositions ap- plicable to 2 x 2 partitions are known for (+), ('_) and (*), each can be extended by recursion to arbitrary n x m partitions (n,m Z 2). 3. 2. Decompositions of the Union and Dot-Composition Qperators By taking the join operator as the analogue of real addition and the dot operator as the analogue of real multiplication, it is obvious that union and dot—composition are analogous to real matrix sum and prod— uct. Furthermore, since union and dot-composition satisfy many of the algebraic laws which are satisfied by their real matrix counterparts, it should not be surprising to find that decomposition analogies exist also. Let R and S be in LXY. By definition, R is (+)-compatible with S. Let {Rij} and {Sij} denote 2 x 2 partitions of R and S, respectively, where,for l S i,j S 2, X1 and Yj are the antecedent and consequent sets, respectively, of Rij and Sij' By definition, Rij is (+)-compatible with sij’ l S i,j S 2. It follows from Definition 1. 8 that for each ordered pair (x,y) in XiY" 1 S i,j S 2, (R + S)1j(x'y) = RiJ-(Xiv) V Sijlxnr) = (R1,. + sij)(x,y). Therefore, the decomposition of the union operator is given by (R +S)ij = Rij +sij , (3.1) 1 S i,j s 2. The suitability criteria for the operand partitions are as follows: For 15 i,j S 2, -. .. ‘ 'rrfi". 49 A(R+S).. = AR.. = A5,. 13 1] 1] C(R+S).. = OR.. = cs. 13 13 Ij where the A's denote antecedent sets, the C's denote consequent sets and the subscripts denote the L- relations to which the sets correspond. The decomposition of the dot-composition operator is slightly more complicated but equally straightforward. Let R and S be in LXZ and LZY, respectively. By definition, R is ('_)- compatible with 5. Let {Rij} and {Sij} denote 2 x 2 partitions of R and S, respectively, such that Xizj is the universe of Rij and 2'in is the universe of Sij’ ls i,js 2. By definition, Ri1 is ('_)-compatible with Slj’ and Ri2 is ('_)-compatible with SZj’ l S i,j s 2. From Definition 1. 9 and the generalized associa- tive law, it follows that for each ordered pair (x,y) in XY, (R -_ S)(x,y) = [ V {R(X,Z) ' S(Z.Y)}] V[ V {R(X.Z) ' S(Z.Y)}l; z€Z1 z€ZZ and hence, for each ordered pair (x,y) in Xin, l S i,j S 2, (R '—S)ij(x,y) = [ V {Rum/2) - Slj(Z.V)}] V[ V {1112092) ° Szj(z,y)}] z€Z1 2622 [(Ri1'—slj)+(RiZ LSZj)](x,Y) . Therefore, the decomposition of the dot-composition operator is given by (R '- S)ij = (R11 #5”) + (R12 '— Szj) , (3. 2) 1 s i,j S 2. The suitability criteria for the operand partitions are A(R'_S).. = AR..‘ C(RLS)“ = C5 11 11 11 C : A ; C 2 AS , il lj 12 2j ii :-. _«.'-. .511 13115 50 Clearly, 3. l and 3. 2 are analogous to the well-known decomposi- tions of real matrix sum and product. Tamura et a1. [T- 1] have alluded to the decomposition analogy for min-composition of J -relations. 3 . 3. flmpositipp of the Reflexive Dot- Tra_n_sitive Closure Operator Using the real matrix analogues of union and dot-composition, it is possible to define a real matrix analogue of reflexive dot- transitive closure. In particular, let B denote an n x n real matrix; then form the finite sum 11 S = Z) Bk n k=O where B0 is the n x n real matrix identity, and Bk = Bk ' 113, k 2 1. (Here 2 denotes real matrix sum and juxtaposition denotes real matrix product. ) If 1im Sn exists then n—>oo 1imSn = E Bk : (I- 13)‘1 Q p(B) n—>oo kZO Where (-) and (-1) are the real matrix difference and inverse operators. Evidently, the operator p is the real matrix analogue of (*). A decomposition of p follows immediately from the decomposition of real matrix inversel. In particular, if {Bij} is a 2 x 2 partition of the real square matrix B and if the matrices a, = p(B11) and I3 = p(BZZ+B (1B 21 12) exist then a 2 x 2 decomposition of p is described by the equations [P(B)]21 : BBZIQ ; [P(B)]22 = I3 ' 1 A derivation of the real matrix inverse decomposition, adapted from Frame [F-3], can be found in Appendix A of this thesis. --«" mg."- : :-ia :rwonx ~Usw .11: or 31193913“;- " _.f_'|_'_-_-__1-_ E 1' " .11". 5" l .'- .7151" 0J1.."".‘ 93: 51 The fact that all quaternary operators in the decomposition of p have L— relation analogues suggests the existence of a similar (*) decomposi- tion. Using formal arguments strongly motivated by the techniques employed in Appendix A, it is shown below that the L- relation analogue of the p decomposition is a valid (*) decomposition. 3. 3. l. A Derivation by Factorization Let R denote a (*)—compatible L- relation and let {Rij} denote any 2 x 2 partition of R such that R11 is (*)-compatible. Using the (+) de- composition, R can be written as R = C +C2+C3+C4 1 where 1 I ' 1 0:0 R1110 0:0 OIRIZ _ _..-_-.--1- ~ -__.__L__- .. -_ '__1_ — -._ ..... - Ci' : ’CZ‘ : ’CB" 1 ’C4‘ 1 ’ R21} 0 0 20 01R2 0: 0 and accordingly, R = (C1+CZ+C3+C4) . 4 ~'< The objective is to factor ( E Ck). in such a way that each factor is the resultant of a regular L- relation operation applied to the Ck's. Further- more, 2 x 2 partitions of each factor should be apparent. If a factor contains an expression involving the finite application of (+) and/or ( )1, exclusively, then any 2 x 2 partition of this expres- sion can be found using 3. 1 and/or 3. 2. It is to be expected, however, 1To improve the readability of the equations that follow, juxta- position ( ) is used in lieu of the symbol '_ to denote dot-composition. This notational change is also employed in Appendix B and in Section 4. 2. 2 of Chapter IV. 52 that factors will also contain expressions of the form >l< 0 :1: A1 0 l l -..... l--——- and I o o:A2 where the l - l L- subrelations of the indicated 2 x 2 partitions are (*)- c ompatibl e. Using 3. 2 and the 2 >1: I I o I : o I : o I I0 ----,L--- = -——4|-—-- , whichimplies ---,L-—- = ___-;__,-. A 1 I A g I A: I A i I Butby 1.10, o:0>'< Igoi‘ IIO —~—4'—-- = -—-f—- = —--:-—-— (3.3) A I 0 A I I A I I Similarly, 0 I A I t A -—~I-——- = ---I—-— . (3.4) 0 I 0 o i I Finally, it follows from 3.2 that, for eachkz l, k k A ' 0 A ‘ 0 l t 1 2 __-..1.___- ___ _---I_-_-_ I I l l k I O . AZ 0 I AZ Therefore, using 3.1, AlIO 1:0 A:0k EAT: 0 ----L--- - ---1-L_-_ 1&0. I _ I + I I ’ OIA 0:1 kzioiA 0 ISA: szo that is, A ‘ 0 A2“ 0 1 1 1: -~—.L---- = ----+‘—— (3.5) I l a. I I m 0 : Az .0 .A.2 idempotency of (+), 53 4 =I< * >I< * During the factorization of ( E Ck) , the expressions C1C2C4, k=1 * >I< v " (CICZ) and (CZC4)>P will emerge. Using 3. 3—3. 5, these expressions can be simplified as follows: 9.: >'.< =I< >I' >'.< >'.< >1: c1c2c4 = c1c2c4+c1c2+czc4+c2. (3.6) That is, :1: . =1: * * R11 : RllRlz = """" ------ """ R211111 : I+R21R11R12 ' I I * I o. o 0 I0 0:R11R12 ano = --+ ---------- + ——————— f“ + "T ——————— ———-;——— . >1< >:< I I ‘ 0:R21R11R12 R21R11: o o. 0 o , I = C1C2C4 + clcZ + 0204 + c2 . Also, (clcz) = C1C2+I, (3.7) as can be seen from 0 t 0 I : 0 >1: ,:< I I (clcz) — -_-----:.-- = ""1"?" ' I I RZIRll' 0 RZlRlll I 0 g 0 I :0 I I :1: ___ _____ >::_:_-- + —-—:--- : CICZ +1 RZIRll : O 0 I I Similarly, ((;:(;4)>'c : CZC4 +I . (3°8) In addition to 3. 6-3° 8, the factorization process will rely heavily upon 54 2 Theorem 3. 1. For 15 ks m1: 9,: * >.'< >}< [C1+C2+C3+C4] = [C1C2C4+C3] {by 3.9} = [clc2c4 + c3]:‘< {by idempotency of ($) and 3. 9} = [clcazzc4 + clc: + CZC4 + c2 + c3]>“ {by 3. 6} a, a,» = [clczc4 + clc + I + Chic + I + C* + C ]>.< {by idempotency Z 4 Z 3 of (+)} 2 = ”192% +(c1c2) + (c2c4) +c2 +c3] {by 3.7, 3.8} = [(c"2‘c4)‘(c2 + c3 + clc2c4)‘(c1c2)‘]‘ {by 3.9} :1: :1: >‘.< * * >l< l : (C2C4) (C2 +C3 + C1C2C4) (CICZ) . 13111: clearly, _ . 1The last step follows after considerable algebraic manipulation 1n Wthh the term in brackets [ ] is shown to be idempotent with respect to dOt‘ Composition. 55 * I R I 0 >I< >I< 11 L (CZ+C3+C1CZC4) = -----: --------- ;-—-—;- . 0 3 (322+R21R11R12) Hence, >1: 4 z}: R = (2 c ) k=1 k I ' R* R R ' o I . o : 11 12 11: g = “-1 ———————— ———-¢ ---------------------- I"- I ' >:: >5< >}< . l o I I o . (R22+R21R11R12) RZIRU. I (3. 10) Once the indicated dot-compositions are performed in 3. 10, the quaternary operators constituting the (=3) decomposition become appar— ent. The suitability criteria for the operand partition are as follows: Forlsi,j52, 3. 3. 2. An Alternative Derivation The preceding derivation, albeit formally correct, requires con- siderable prescience with regard to the form of the decomposition sought. An alternative derivation is now given which requires no such foresight. Some of the ideas used in this alternative derivation have important implications beyond the solution of the decomposition problem. To begin, 1. 11 iInplies that I I >1< >I< >:< I I (R )12 (R )11: (R )12 R11 { R12 1:0 ------ I—‘—‘—“-‘ "‘ ‘—_-~-I---~——- —-—--'—-—- :'< >': :‘: ' :': | I ' ‘ i . I I (R )21 ' (R )22- (R >21. (R )22 R21:13‘22 0 ' I whereupon using 3. l and 3. 2, 56 x11 = xllR11 +x12R21 + I (3. 11) x12 2 x111112 +x12R22 (3°12) x21 = x211111 + x22R21 (3' 13) x22 2 XZIRlZ + XZZRZZ + I , (3. 14) where xi]. = (R*)ij, 1 s i,j s 2. Evidently, the (’1‘) decomposition prob- lem can be solved by solving the set of simultaneous equations 3. 11- 3. 14. To do so requires the capability of solving an equation of the form x=xA+B, (3.15) where A, B are known L- relations. That a solution of 3. 15 exists can be seen from the following theorem due to A. Tarski [T— 2]. Theorem 3. 2. Let L be a complete lattice, and let f:L—>L be a monotone nondecreasing function. Then the set P of all fixpoints of f is nonempty, and the algebra (13,5), where S is the partial ordering on L, is a complete lattice with greatest element £ub{x€L’f(x) Z x} and least element gIb{xeL|I(x) s x} DD Observe that the lattice LXY is complete. Moreover, observe that the function f(x) = xA + B, on LXY, is monotone nondecreasing. Therefore, according to Tarski, f has at least one fixpoint; and by definition, any fixpoint of f is a solution of 3. 15. By applying the technique of iteration, it is seen that Xf=BA 57 is a fixpoint of f. For let xk=x A+B k-l for k 2 1, where x0 = 0. Then for each k 2 0 k . xk = B( 2 AJ) , 1:0 where A0 :1 and AJ =AAJ-1, j: 1; and so limxk =x . Thatx is a k—>oo f f solution of 3. 15 can be seen by substitution: BA* = xf = fo+B = BA*A+B = B(A"A+I) = BAm. Finally, notice that xf is also the least fixpoint and hence the least solution of 3. 15. For suppose that x denotes the least fixpoint of f. It follows that f =§A+B = (xA+B)A+B = §A2+BA+B = =§Ak+1+BAk+BAk'1+... +BA+B k. = §Ak+l+B(EAJ) 1:0 for each k 2 0. But this implies that BA>5 S _x. Thereforex = BAzF : xf. Using the least solution of 3. 15, it is ascertained from 3. 11 that X11 = (X12R21 + I)R11 = XIZRZlRll + R11; (3°16) and from 3.13, x21 = (x22R21)R11 : X22R21R11‘ (3'17) Using 3. 16, 3. 12 becomes x12 =X1Rz(R21k11R12+R2-2)+R11R12 which has least solution x12 = R11R12(Rzz + R21R11R12)* ' (3°18) 58 Substitution of 3. 18 into 3. 16 yields >I< >I< >I< =1: :1: x11 = R11 + R11R12(R22 + R21R11R12) R21R11 ' (3° 19) Similarly, using 3. l7, 3. 14 becomes x22 = x22(R21R11R12 + R22) + I ' which has least solution >i< >1: x22 = (R22 + R21R11R12) ’ (3'20) Substitution of 3. 20 into 3. 17 yields x21 = (R22 + R21R11R12) R21R11' (3°21) Observe that 3. 18-3. 21 agree with the result obtained by carrying out the indicated dot- compositions in 3. 10. 3. 3. 3. Special Cases Several special cases of the (*) decomposition warrant considera- tion here because of their importance to the applications. For the pres- ent, however, these cases are discussed in a purely mathematical context. Chapter V of this thesis is devoted exclusively to applications. Consider first the symmetric, (*)-compatib1e L-relations (Cf. Definition l. 10 ii). It follows from the definition of (*) that if the (- ) operator on L is commutative then R):< is symmetric whenever R is symmetric. With regard to the general (4‘) decomposition, (- ) com- mutative and R symmetric imply the following: (R*)11 = [(R>k)11]c, (R*)12 : [(R*)21]C and (R*)22 = [(R>::)22]C. When symmetry can be assumed, the computational complexity associated with the (’1‘) operator is halved. The next class of (*) compatible L-relations to be considered are those which have partitions of the form 59 R:R I 12 T I ’ l 0 3 R22 where Rii(i=1, 2) has the upper triangularity property. That is, Rii(x,y) = )1 for x > y. Here 5 is understood to be a total ordering on the antecedent (and consequent) set of Rfi. Munro [M— 1] showed, via graph—theoretic reasoning, that for a finite 2-relation of this type I 9,: :k I >1: a}: R11 : R12 R11 { R11R12R22 ---—.—-——— = u". —————————— . (3.22) ‘ ' >1: 0 : R22 0 : R22 From the (*) decomposition equations (3. 18-3. 21), it is evident that this result holds for L-relations. Moreover, the R11 need not possess the upper triangularity property. Fischer and Meyer [F- 1] made the interesting observation that conjunction composition can be performed via the reflexive conjunction- transitive closure operation and 3. 22. This same observation can be made more generally for L— relations. Let A and B denote the L— rela- tions which are to be dot-composed. From 1. 10 and 3. 22, it follows that 01A:0* IIA:AB ~--*I--—-I--- ““l"—":"——" 0.0:13 =021nB. (3.23) ---+---f--- -*-!-~--! ----- o : o : 0 o : 0: I In connection with the shortest path problem (cf. Chapter V), Hu [H— l] devised an algorithm which can be adapted to the task of find- ing the reflexive dot- transitive closure of an L—relation having a par- tition of the form 60 I I R11 . R12 I 0 ..... 1.----- --__- I I : ' I R R21: 221 23 ' -____:_-.__. —I—— _ _ o g R :R where the Rij are n x n. The Hu Algorithm is described briefly as follows: T and W denote n x n 10m arrays; U and V denote 2n x 2n 10m arrays with 2 x 2 partitions {Uij }, { Vij}’ respectively. Initially, I I R11 1 R12 R22 ; R23 U : -—--—. ————— , V:= ----- r ----- , I I R21 : R22 R32 : R33 Step 1: U = Ua= , Step 2: Vllz= U22; V2: V ; * Step 3: UZZ— V11 , U:_ U , Step 4: T:: U12V12; W:= V21U21;end I I U11 I U12 ; T .I. ---__l ~~~~~ r-'-— I“ I R U21 : V11 : V12 _____ I_-----I--.-_-- I l W l V21 I V22 The point to be illustrated here is that the Hu Algorithm is in- efficient. This is done by comparing the number of 10m operations required by the Hu Algorithm with the number of 10m operations im- plied by the (*) decomposition equations in this special case. However, instead of performing the (*) operation recursively, an iterative pro- cedure based upon the factored form (3. 10) will be employedl. 1In Chapter IV, this iterative scheme will be generalized to ar- bitrary p x p partitions. 61 Let I Q11 ! Q12 R = ..... + ______ 9 I Q21 : Q22 where Q11 ‘ R11 Q12 ‘ [R12 ' 0] I R21 R22 : R23 _ ...... _ _____ l _____ Q21 Q22 : 0 R32 : R33 Using the factored form of the (*) decomposition, R:':=UDL l 1 l ’ where z: I I :R11R12 I O -__-, ........ l _ l I --_J ________ L--- . l 0 1' O I I :1: I R11: 0 D1 = """ ““““ 0 I[Q22+021R11012] I I O : 0 _ _______ _I.-__'-.__ I I l I L1 ‘ R21R11I 1:0 _________ I_-_I___ I 0 : 0: I The factored form can be used again to evaluate [Q22 + Q21R11Q12] , and the resulting upper and lower triangular factors can be absorbed into U1 and L1’ respectively. The result is a 3 x 3 factored form R = UZDZLZ . 62 where 1'R*R 'R*R (R +R R*R )*R . 11 12 i 11 12 22 21 11 12 2§_ -- . ........ .-___-_-_____- ___ -_-_ >'.< >1: ._ I I U2 ‘ 0 ; I ; (R22+R21R11R12) R23 ““r““"—r _______ , ................ o g o ; I :1: I FR”: 0 . 0 _-__J _______________ i ......................... I :1: >:: | __ I D2 ‘ O 1(R22+R21R11R12) : 0 “‘*‘.—““‘*‘-“‘"“"‘t “““““““““““ g """" :*"2: ‘ 'I‘ 'I‘ '1‘ - 0 1 0 I‘R33+R32(R22+R21R11R12) R23) ' 1 T 0 j 0 __________________________ l____---__._----____I__1___ I _ I L2 ‘ R21R11 ; I i 0 _--____..__-.-_ ._ ‘-""'"‘-"r _________ . ________ .-__|_-_- :;< :1: >z< . 2:: *1 LR32(RZZ+R R R. ) R R . R32CR22+R R R12) ,1 21 11 12 21 llI 21 11 The computation of R):< using the 3 x 3 factored form requires three (*) operations involving n x n operands and nineteen dot-composi- tions involving n x n operands. If Algorithms Z. 2 and 2. 4 are used to perform these operations, approximately 44n3 [om operations are needed. By comparison, the Hu Algorithm requires three (=3) operations involving Zn x 2n operands and two dot-compositions involving n x n operands for an approximate total of 52m3 10m operations. It should also be noted that computation using the 3 x 3 factored form requires 25% less main memory than is required by the Hu Algorithm. The final special case to be considered results from a particular way of partitioning an arbitrary (*)-compatible L-relation. Specifically, consider the 2 x 2 partition R11E 1'12 R = _.._11._.“ , r21 3 p22 63 where p22 is an L- relation whose antecedent and consequent sets are singletons. Applying the decomposition equations yields >.'< >:< =1: >:< >1: . =l< =.'< >l< * R11+R11r12(922+r21R11r12) T21R11 2 R11r12‘922+r21R11r12) R = -°------“--“-: ----------------- I‘ “““““““ ' """"" . ,I‘ >:< >,'< : >:< * (922”21R11r12) r2113‘11 : (922+r21R11r12) However, by l. 10 (922 + r21R11r12) = (Y + “’22 + r21R11r12” : Y = Y ’ where y is the greatest element and multiplicative identity of the [cm L. It follows that R11+(R11r12)(r21R11) I R = ————————————————————— 'r ———————— . (3.24) : r21 In case R is n x n and Rll is known, the nuInber of 10m operations re- quired to compute Ra< is just 12(11-1 2). .,-; ='I'.'7I'- [l-L.,:r,-}q='nU-g . -.__‘-:1.-, 1.5335 9...),rw -' I -.‘u' "'F'Ji' .'~'. - -'- .-.:: .L:-'3 '1- CHAPTER IV DEC OMPOSITION- BAS ED ALGORITHMS This chapter examines the efficacy of using decomposition—bas ed algorithms to operate upon L- relations which are dimensionally-larger than available main memory. First, it is shown that each recursive decomposition derived in Chapter 1.11 implies exactly the same number of 10m operations as was seen to be sufficient in Chapter 11. Next, the recursive decomposition equations are converted to iterative decomposi- tion equations, and algorithmic embodiments of the latter are given. It is shown that these algorithms are efficient not only with respect to the number of Zorn operations performed but also with respect to the num— ber of seeks required. 4. 1. On the Number of 20m Operations Implied by the Recursive Decompositions Let Nu(2n) denote the number of [om operations implied by 3. 1 When the o erands are an x 2n. 1 Obviousl N is described b p Y. u Y n n- 1 Nu(2 ) _ 4Nu(2 ) . Using the initial condition Nu(20) = l, the preceding recurrence equation has for its solution n Nu(2 ) — 2 : \_________ 1So as not to obscure the analysis which follows, operands are assl-ln‘led to be 2n x 2“, where n is an arbitrary positive integer. 64 65 which is exactly the complexity exhibited by procedure union (Algorithm 2. 1) for similarly dimensioned operands. Next, let Nc(2n) denote the number of 10m operations implied by 3. 2 when operands are an x 2n. Clearly, NC is described by n _ n- 1 A n-l NC(2 ) — 8NC(Z )+4Nu(2 ), which has for its general solution n- k-l n n 0 n-1k N(2):8N(2)+4E8N(2 ). c c _ u Upon substituting the initial condition Nc(20) = 1 and using the previously derived function for Nu’ it follows that Nee") = (2)123n)- 22“, which is exactly the complexity exhibited by procedure comp (Algorithm 2. 2) for similarly dimensioned operands. Finally, let Nt(2n) denote the number of 10m operations implied by 3. 18-3. 21 when the operand is 2n x Zn. After some consideration, it is apparent that Nt is described by Nt(2n) = 2Nt(2n'l) + 4N (2n‘1)+ 2N (2n'1)+ 2N (zn‘l) , c c u l 2 l where c (Zn) 2 23n+1 - 22n+1 is the number of 20m operations needed 1 t0 perform dot- composition when one of the operands is reflexive; N (2n) : 23n+1 — (3)(2.2n) + 2n is the number of 10m operations c 2 needed to perform dot-composition when only off-diagonal entries of the resultant are required; and N11 (Zn) 2 Elm - Zn is the number of 20m operations needed to PQrform union when only off-diagonal entries of the resultant are required. 66 Using the initial condition Nt(20) : O, the preceding recurrence equation has for its solution N42“) = (21(23n)- (6)122“) + (4)02“) . which is exactly the complexity exhibited by procedure trans closurel (Algorithm 2. 4) for a similarly dimensioned operand. 4. 2. Iterative Algorithms with Adjustable Main Memory Requirements Since MALGOL does not support recursive computation on arrays which are dimensionally—larger than available main memory, it is necessary to convert the recursive decomposition equations to iterative decomposition equations which operate directly on the L- subrelations of pxp partitions. These conversions are carried out in the subsections which follow. Algorithmic embodiments of the resulting iterative equa— tions are created and analyzed. 4. 2. 1. Procedures for Union and Dot-Composition Let p and d denote arbitrary positive integers, and let R and S denote pd x pd L-relations. Furthermore, let {Rij} and {Sij} denote pxp partitions of R and S, respectively, where Rij and Sij are dxd L- subrelations, 1 S i,j S p. By simple induction arguments employing 3. l and 3. 2, it follows that for 1 S i,j S p (R + 5),). = Rij + sij (4.1) P (R ‘- S)ij = kEI(Ri-k _ Skj) 6 (4o 2) Equations 4. l and 4. 2 are identical in form to the definitions of union and dot-composition. Except, in lieu of the join and dot- operators, there appear the union and dot-composition operators; and, in lieu of ”ram 1!. A ) 67 operands which are torn elements, there appear L— relation operands. Thus, procedures based upon 4. 1 and 4. 2 will resemble Algorithms 2. 1 and 2. 2. In the algorithms which follow, it is assumed that the contents of each 10m auxiliary array has a pxp partition whose L—subrelations are dxd. Moreover, the contents of each 10m auxiliary array is presumed to be stored by L— subrelations of its pxp partition. The procedures which communicate L- subrelations between main and auxiliary memory are adequately described by their headings, respectively, read(i,j):subarray of 10m aux array(R):into [om main array (A) write(C):, an 10m main array,into the (i,j):subarray of 10m aux array(Q). Owing to the way in which the contents of 10m auxiliary arrays are stored, it is apparent that read and write procedures can be created which require only one seek per call. Algorithm 4. l procedure i-union(R,S,Q,p,d); value p, d; integer p, d; [om auxiliary array R,S, Q [l:pxd, lszdl; comment A call to i-union results in Q = R+S; comment This procedure requires 3d2 10m words of main memory; begin integer i,j; JZom main array A, B,C[l:d, l:d]; _fprj: l s ep 1 until p do _fo_r i:= 1 step 1 until p begin read(i,j,R,A); read(i.j.S,B); union(A,B,C,d); write(C,i,j,Q); léLl end end i- union In Algorithm 4. 1, procedure union (Algorithm 2. 1) is encountered p2 times, while procedures read and write are together encountered a total of 3p3 times. Therefore, the complexity of procedure i-union is (pd)2 + 3p2cr. 'inoq’q . .I'I 'U'-+ "" 68 Alg orithm 4. Z procedure i- comp(R,S,Q,p,d); value p, d; integer p, (1; 10m auxiliary array R,S, Q[l:pxd, lszdl; comment A call to i-comp results in Q = R '— S; . . Z . comment This procedure requires 3d tom words of main memory; begin integer i,j,k; 10m main array A, B, C[1:d, l:d]; for j:= 1 step 1 until p519 m i:= 1 step 1 until pig begin comp(A, B,C,d); if p=1 32 32 W: Eh: 2 step 1 until p2 begin read(i, k, R, A); read(k,j:s’ B); compunion(A, B,C, d); 2112 W: write(C, k,j, Q); end end 1. com?— In Algorithm 4. 2, procedure comp (Algorithm 2. 2) is encountered p2 times ° procedure compunion (Algorithm 2. 3) is encountered p2(p- 1) ’ tme s ‘ and procedures read and write are together encountered a total 0f 2P3 + p2 times. Therefore, the complexity of procedure i-comp is 3 Z +p )0'. Z‘Pd>3 - (pd)Z + (2p In connection with Algorithms 4. 1 and 4. 2, several points deserve me ntion_ First, notice that the number of 10m operations performed in e aCh case is exactly the number which would be performed by the cor I.esponding Chapter II algorithm, were it possible for the pd x pd ope r a’Ilcls to fit in main memory. Thus, from the standpoint of Zorn ope r a-tions performed, Algorithms 4. l and 4. 2 are efficient. Next, ob- ser V6 that the number of seeks required in each case is dependent upon P 131.11: ihdependent of d. This means that the number of seeks required is 1‘ § 1 ated not only to the dimensions of the L—relations being operated M : #1124111 . ............_ , V L .9. -1151: LE3?!“ . . ‘3 69 upon but also to the amount of available main memory. If pd = constant, p is minimized by making d as large as possible in accordance with available main memory. Resultingly, the number of seeks required is minimized. Thus, Algorithms 4. 1 and 4. 2 are also efficient with re- spect to the number of seeks required. Finally, note that the operands and L- subrelations of operand partitions were chosen to be square only for convenience; similar algorithms exist which admit rectangular arrays. 4. 2. Z, An Iterative Procedure for Reflexive Dot— Transitive Closure Let R denote a (*)- compatible L— relation and for each k _>. 2, let {Rij(k)l1 s i,j S k} denote a kxk partition of R. Moreover, let these partitions form an embedding; i. e. for l S i,j s k- 1 Rij(k + l) = Rij(k)' Next, for each k 2 2 and 1 S l! < i,j S k define iteratively1 (1+1) _ (1) (1) (1) * (1) 61]. (k) — 51,- (k) + 6i! (k)[6M (k)] 6“- (k) (4.3) where (1) _ . . éij (k) - Rij(k)’ 1 s 1,) s k. It will be shown by induction that for each k 2 2 there is a factor- ization of R75 of the form cl, ,,s R = U(k)D(k) L(k) (4.4) where: U(k) is reflexive, block upper triangular; D(k) is block diagonal; and L(k) is reflexive, block lower triangular. Moreover, it will be shown that these factors have kxk partitions whose non- trivial L— subrelations can be defined in terms of the 6§§)(k) as follows: 1Throughout this subsection dot-composition will be denoted by juxtaposition. 70 i) [D(k)]ii = [6§§’(k)]* . 1 s is k (4.5) ii) For 1 S i S l '< . I I 0 1 I 0 l [R22+R21Ri1R*12] R21R11 3 I (4.8) To obtain a refinement of this factorization, one need only apply the 2x 2 factored form to a 2x 2 partition of the L-subrelation [R22 + R21R11R12] I 0322033 This results in 71 1 * 1 Q" = --—)—-——--—--- ----- )— ---------- - ------ --—-—----:—-»-- : I * >:< >1: 1 0 ' I 0 : [Q33m32022923] Q32922 I I (4.9) Now by suitably partitioning the L- subrelations in the upper and lower triangular factors of 4. 8, as * I >'.< P21 R11R12 = [P12 I 1313] and R21R11 = ""‘"' ’ P3 1 the upper triangular factor of 4. 9 can be absorbed into the upper tri- angular factor of 4. 8; similarly for the lower triangular factors of 4. 8 and 4. 9. The result is a 3 x3 factored form of R4. To wit, l l I IIU12,U13 D11,0:0 1.0:0 __L_-___'__-.- _____ '-___J._--- ....L.... --_ ' ' l i i ._ l I R _ 0'1,U23 0.DZZ,0 L21.I:O , ..-_1._- IL---_ _--__:_-_,--:..._--_ _____ L _____ ,-_-_ g I I I I l 1 o: o: 1 0 , 0 ,D33 L31IL32'I where D11 R11’ D22 = sz’ D33 : [Q33 + Q32Q22023] U12 2 1312’ U13 2 P13 + P12Q22023’ U23 z Q22(223 L21 2 1021’ L31: 1331+ Q32022P21’ L32 = 032022“ Equations 4. 3 and 4. 5-4. 7 generalize this process to a kxk factoriza— tion of Rx. The following is a proof of 4. 4 by induction on k: Basis. k = 2. Using 4. 3, the 2x 2 factored form of R,“ can be written as 72 where A = 16§1I*’(2)] = [13(2)] 11 11 A12 = [6‘11’(2)]* 5”,)(2) = [D(2)]116‘11z’(2) = [6(2)]‘22’ = [U(2)]12 _ (11) (1) _ (1) _ (2) A21 — 6 (2)16 (2)]* — (2)[D(2)]11 — [15(2)]21=[L(2)]21 622 = [6111(2)+611)(2)[6(1)(2]*(111(2)]*[=6122)(2)]*= [13(2)]22. So in case k = 2, the Factorization 4. 4 is valid. Induction step. k = p + 1. Assume as the induction hypothesis that 4.4 is valid for k : p. Note that because the partitions of R form an emb edding , (I) _ (l) 6ij (P+ 1) — 61,- (P) for 152 3 2(p-J)= 2(1—1)(p-1)=(3) i=1j=i+1 i=2 P‘1 +1 21(p-1) = (‘13 ). i=1 Therefore, g = pT + 4(§)a + [2(P:1) + 4(3)] (3 + [16(p:1)+p +2](r Now since T = 2d3- 6d2+4d, it follows that 3 2 2 8 5 C = 2(pd) — 2(pd) +4(pd) - 4pd + @113 _ 3p + 2)., . From the preceding complexity analysis, it would appear that the number of [om operations required by procedure i- transclosure is in excess of the number required by procedure transclosurel for a simi- larly dimensioned operand. Actually, as it stands, i-transclosure is doing more work than is necessary. This is evidenced by the fact that less costly procedures can be used when one of the operands in a dot— composition is reflexive or when only the off- diagonal elements of a dot- composition- union are required. The inclusion of such procedures was avoided so as not to obscure the basic workings of the algorithm. However, if such procedures had been used,the number of 10m operations 80 required by i-transclosure would be exactly the number required by transclosurel for a similarly dimensioned operand. (See the analysis of the (*) decomposition in Section 4. 1. ) Thus, it may be concluded that i- transclosure is efficient with respect to the number of 10m opera- tions required. Obviously, Algorithm 4. 3 has an adjustable main memory require- ment, and this allows the number of seeks required to be minimized. Nevertheless, J. S. Frame has pointed out that a further reduction in the number of seeks required can be obtained if one is willing to bypass the creation of a factored forml. The method suggested by Frame con- sists of two steps. The first step is identical to step 1 in Algorithm 4. 3; i. e. , the following transformation is performed iteratively: 22 “21 I “22 where “11: 3411,1112 = HuMlz' #22 2 M22 * M211112 and “21 : M21“11' From the preceding analysis, this step requires on the order of p3 seeks. The second step, substituted in lieu of steps 2 and 3 in Algorithm 4. 3, consists of the following transformation performed iteratively: (‘11 ; “12 @ “111“12H22F‘21 i“12“22 I “21 “22 “22“21 This step requires on the order of§p3 seeks. Therefore, the total number of seeks required by both steps is on the order of%p3. Asymp- totically, this is a 12 1/2% improvement over the requirement of Algorithm 4. 3. l . Private correspondence. ' . 1 . .. . 5' r.' i_f) t1 . I III-Il_. I _u ll CHAPTER V APPLICATIONS This chapter focuses upon three computational problems which can be solved using L—relation operator algorithms. First to be con- sidered is the problem of finding the lengths of all shortest paths in the digraph generated by a distance function. This problem is shown to be solvable using an operator dually related to the (*) operator. Next, the hierarchical clustering problem is defined within the context of J- relation theory, and the relationship between reflexive min- transitive closure and single linkage hierarchical clustering is revealed. Finally, a fuzzy decision—theoretic problem is considered, viz. the problem of finding a system control policy which optimizes the confluence of a fuzzy goal with a set of fuzzy constraints. 5.1. The Lengths—of—Shortest-Paths Problem Let X = {1, 2, . . . ,n}, where n is an arbitrary positive integer; and let D:XZ —> [0, 00) be any function such that D(k,k) = O for each k in X. D is said to be a directed distance function over X1. The digraph generated by D, denoted G(D), consists of n nodes and n2 edges, with D(i,j) being the length of the edge from node i to node j. An l—edge path in G(D) from node i to node j is a sequence of edge lengths of the form p(i,j;JZ) : {D(i,il),D(i1,iZ),...,D(i,_1,j)}; 1Directed distance is more general than metric distance since the latter must also be symmetric and satisfy the triangle inequality. 81 82 and the length of p(i,j;£) is the real sum of its edge lengths. That is, length [p(i,j;1)] = D(i,i1) + D(11'12)+ + D(i,_1,j) , where (+) is the real addition operator. Let D1 be another designation for the directed distance function D; and consider the function D2:X2—> [0, 00) defined according to D2(i.j) = min{D1(i.k) + D(k,j)} k€X for each ordered pair (i,j) in X2. Obviously, D2 gives the lengths of shortest 2- edge paths in G(D). By induction, it follows that the lengths of shortest I-edge paths in G(D), I Z 2, are given by the function D, :X2—> [0, 00) such that D1(i,j) = min{D, l(i,k)+D(k,j)} k€X ' for each ordered pair (i,j) in X2. Evidently, the lengths of shortest paths in G(D) are given by the function D,<:X2—>[O,oo) such that D*(i,j) : min{D,(i,j)} (5.1) 121 for each ordered pair (i,j) in X2. The subscripted * appearing in 5. 1 may be regarded as a unary operator which maps a given directed distance function D into the func- tion D*. Algorithms for performing this operation can be obtained from the (*) operator algorithms simply by replacing each (V) operation by a min operation and each (- ) operation by real addition operation. Upon implementing these changes, transclosurel (Algorithm 2. 4) be- comes Floyd's Algorithm [F— 2], and transclosure2 (Algorithm 2. 5) be— comes Yen's Algorithm [Y- 1]. The conversion of i-transclosure (Algorithm 4. 3) to a lengths-of—shortest-paths algorithm results in a general partitioned computational procedure not heretofore known. Note, 83 however, that the total number of additions and comparisons required by this procedure is in excess of the number required by Yen's Algorithm. 5. 2. The Single Linkgge Hierarchical Clustering Problem A hierarchical clustering scheme (HCS) is any algorithm which, given a symmetric matrix of pairwise similarities between objects in a finite set X, produces a hierarchy of partitions of X. For the clustering objective known as single linkage hierarchical clustering, several al- gorithms are available [J- 1, G-3]. The purpose of this section is to show that yet another single linkage HCS exists in the form of the re- flexive min—transitive closure operator. First, however, it is necessary to define the hierarchical clustering problem within the context of J- relation theory. X2 In [Z-3], it is shown that each R 6 J admits of a resolution in terms of its distinct B-cutsl; i. e. R=Z(3R, B (3 0 < (5 s 1 , (5. 2) where 2 denotes J-relation union, and juxtaposition denotes real multi- plication. Also in [Z-3], it is shown that if the B— cuts appearing in 5. 2 are conjunction— equivalences over X, then R is a min- equivalence (cf. Definition 1. 10); and conversely. So by virtue of the fact that (5— cuts 1The [3-cut of R 6 J'XZ, denoted RP, is a Z-relation with universe X2 such that, for each ordered pair (x,y) in X2, R (x,y) = 1 iff R(x,y) 2 (3. It is understood that, in 5. 2, to each R there corresponds a unique (3. In case (31 % (32 and R,3 = R,3 , the coefficient of R6 = R 1 = R is set to (3 = (31 V (32. In so doing, 5. can be converted to a form in which to each R there corresponds a unique (3. The resulting Rfi's are the distinct (3- cuts. 84 form an embedding, i. e. [5 < (3' implies R,C R , (3 F5 the concept of min- equivalence is mathematically synonymous with the concept of a hierarchy of partitions. Moreover, any operator (A) which A maps a finite, symmetric R 6 IX into a min— equivalence R 6 JX can be regarded as a HCS. Using a dual of the argument appearing in [G-3], it follows that any single linkage HCS results in an R which describes the strengths of maxi-min chains in the digraph generated by R. That is, for each pair (i,j) of nodes in G(R), i f j, R(i,j) = max max sk (i,j) , 1221 k, 1 where Sk is the minimum link strength in the k1i1 I-edge chain from node i to node j. From the graph—theoretic interpretation of the (*) operator, it is apparent that the reflexive min-transitive closure oper- ator describes a single linkage HCS. As a data structure analysis technique, the (‘4‘) operator is of little value. This is because a min- equivalence unnecessarily specifies the strengths of relation between all pairs of objects; whereas, for cluster- ing purposes, all that is required is the strengths of relation between partition blocks at each level in the hierarchy implied by the min- equivalence. This latter information is efficiently coded using a tree- like structure called a dendrogram. As Gower and Ross [CE-3] have Shown, single linkage hierarchical clustering can be performed in on the order of n2 comparisons and additions when the output is displayed as a. dendrogram. By comparisonfthe most efficient (*) operator II"I:rII.1‘: 85 algorithm requires on the order of n3 comparisons; and, even then, the output is not in a form permitting visual interpretation. 5. 3. A Problem in Fuzzy Decision Theory Consider the following fuzzy decision problem adapted from Bell- man and Zadeh [B— 2]: A discrete-time, deterministic system S with finite state space X and finite input space U has a state transition function f:XU—+X. Further- more, there is a set T g X with the property that for each x in T and u in U, f(x,u) = x. That is, T is comprised of the terminating or absorb- ing states of S. The admissibility of an input when S is in state x is described by the J—set CX on U. The goal of S is a J-set G on T. The objective is to control the system S from an initial state xO to a termi- nating state x in such a fashion as to maximize the confluence of goal N and constraints. More concretely, for a given initial state x0 the con- fluence of goal and constraints-~sometimes called a decision at x0--is a J- relation defined by DXO(u0,ul, . . . ,uN_1) = CXJu0)ACX1m1)A... ACXN_JuN_1)ACXxN) 6.3) Where u . . ,u is a sequence of inputs which carries S through 0’u1" N-l the sequence of states x1,x2, . . . ,xN. The termination time N is im- plicitly defined, but it is tacitly understood that for t < N, x1: is in T', the complement of the absorbing set T. To maximize a decision at xO it is necessary to find a sequence of inputs u0,u1, . . . ,UN 1 which yields a maximum value of the function DX in 5. 3. Of course, if T is not 0 reachable from x0,then DX is assumed to be identically zero. 0 1 cm: :1-zrfl 86 The solution of this problem is given in [B-Z]. The important steps may be summarized as follows: Owing to the time invariance of S and the time independence of the goal and constraint sets, 5. 3 can be written as Dx0(u0,u1, . . . ,uN_ 1) = Cx0(uo) A Dxl(u1,. . . ,uN_ 1) (5. 4) where x1 = f(x0,u0); and the termination time N is a function of x0, and the termination condition: xo,x1, . . . ,xN_ 1 belong 110’“1"" ’uN-l to T'. Now suppose the function 11:T'—> U denotes a policy for selecting inputs based upon the state of S at each input selection time; i. e., n(x) is the input that should be applied according to policy rr if S is in state x. Since u0,ul, . . . ,uN_1 are determined by x0, TI' and the transition function f, 5. 4 can be written concisely for all possible initial states as a functional equation of the form D(TT) = C(Tr) fl P(Tr) A D(W) (5. 5) where: . . . .th _ 1) D(TT)1S an n x l J—relation whose 1— component IS Dg.(1T), 1 the decision at £1 subject to policy 1T. It is understood that D§(Tr) = (3(5) for g in T and all 11'. ii) C(TT) is an n x 1 J-relation whose i£1 component is Cg (F(Ein, the admissibility of input n(gi) given g, as the current1 state of S. For g in T and all 1T, Cg(n(§)) = 1. iii) P(1r) is an n x n J-relation defined by 1 fig. :f(g.,w(§.)) [P(+r)](i,j) = J 1 1 0 otherwise. iv) The operator (0) denotes intersection of J-sets, andA denotes min- composition. 87 In [B- 2] it is shown that 5. 5 has a unique solution for each 1r. Moreover, it is shown that there exists an optimal policy 4?, optimal in the sense that, for any other policy 11 and all g in T', DEG) Z Dghr) . So in other words, the fuzzy decision problem is one of choosing the optimal policy from among the In1 possible policies, where m is the size of U and I is the size of T'. Clearly, the optimal policy can be deter- mined by first finding /\ D = max D(TT) 11' and then using 5. 5 to determine n(xt) for each state x0,x1, . . . ,xN_1 in the sequence which leads to the terminating state XN. For the optimal policy, 5. 5 becomes ’15 = max [C(11) (1 pm A 13] . 11' In particular, the optimal decision at g, in T' is given by DE- : :1 {c €11” )ADf(gi’a_)} 1 J I = [k v [av {cg ipm )AD }]]v[v {cgi (a. Jij)/\G(£(g,a ))}] k:1pk 13k}j=1 Where a is any input such that f(§., c1 ) = g with g in T'. Further— pk 1 pk k k more, it is understOOd that G(x) = 0 for all x in T'. Using the distribu- tiVity of A over V, A 1 D : O. gi [k3111avcéi1pk )lAng}]v [jv{cgimjmcueyajnfl pk This equation can be written more concisely for each g in T' as follows: 62B£6+F (5,6) 88 where 6, F are 2 x 1 J- relations and B is an 1 x 1 J-relation. Further- more, for 1 S i,j S 1 5 ’13 1 gi m l". = V {C (a )AG(f(§.,a ))} 1 k=1 gi k 1 k 0 if there is no a such that f(§., a ) = g. B.. : Pj 1 PJ- J 1’] VC ((1 ) otherwise. a £1 Pj pj The solution of 5, 6 is 6 = 13* A I‘. This solution can be obtained by either of two distinct methods: i) As suggested in [B— 2], 5. 6 can be solved via 12 iterations of 6(k+l) = B A 6(k)+1“ , where 6(0) = (0,0,... ,0)C. The [El-1 iterate, 6(1), equals 13* A F. ii) First B* is computed and then B* A F is computed. In the case where B can fit in available main memory there is little difference between the computational complexities of either method. Using Algorithms 2. 1 and 2. 21, method i requires (1-1)(212) : 2(l3 - [2) 130m operations; whereas, using Algorithms 2.2 and Z. 5, method ii re— quires (313 + £2)/2 fom operations. When, on the other hand, B is dimensionally—larger than available main memory, method ii offers a distinct advantage over method 1 in terms of the number of seeks required. For concreteness, suppose that B is stored in auxiliary memory as a 1It is understood that, although these algorithms have been writ— ten for square arrays, modifications to permit rectangular arrays can be rhade without difficulty. The same understanding applies to Al- gor ithms 4. 1 and 4. 2. ‘m—m, 89 p x p partition with d x d blocks. Using Algorithms 4. l and 4. Z, on the order of dp3 seeks to auxiliary memory are required by method i; whereas, using Algorithms 4. 2 and 4. 3, method ii requires on the order of 3P3 seeks. The number of 10m operations required by both methods is approximately the same. In several situations, independent of the dimensionality of B, method ii is preferred over method i. Consider the most obvious situ- ation in which B remains fixed while I“ ranges over several J- relations. This happens when optimal decisions are sought for different goals. Clearly B* need be computed just once. Other situations arise where B is altered slightly. For example, the transition function of S might be modified to admit a gi to gj transition where previously no such transition was allowed. In this case, the i-j element of B is increased from zero to V C (Qp.)’ and a new matrix—B— is formed: g. up. 1 J J "B = B + a A p where a, f) are I x l and 1 x I J- relations, respectively, with com- ponents O k ;é i O k ;éj l k:1 — VC§(Q) k2.) A simple argument shows that :1: (3):“: = (B + a A (5);“ = 13* + (3* A a) A (p A B ) Therefore, if B:‘( is known, the computation of (Bf: requires only 2122 - 1 10m operations; and, hence, the computation of (Bf< A 1“ requires only 2. 4f — 3!! 20m operations. Another example where B is altered slightly 0CChrs when the state space of S is augmented with a new non-terminating 90 state. In this case a new row and column augment B to form a matrix * Ba' The computation of Ba can be performed using 3. 24 in subsection * 3.4. 3 of this thesis. If B is known, only 12(g) 10m operations are required to compute B; CHAPTER VI CONCLUSIONS This chapter summarizes the main results of the thesis and sug— gests future research. 6. 1. Summary The objective of the thesis was to analyze the computational com— plexity of certain L- relation operators, viz. union, dot-composition and reflexive dot-transitive closure. This necessitated the creation of algorithmic embodiments in accordance with a model of computation. The model employed for this purpose was fashioned after the notion of discrete- time, sequential computation generally associated with real- world digital computers; however, lattice-ordered monoid (f om) opera- tors were assumed to be atomic. The stipulation of a finite-size main memory and potentially unlimited-size auxiliary memory facilitated the consideration of algorithms which operate on dimensionally-large L- relations. For such algorithms, computational complexity was measured not only by the number of 20m operations performed but also by the num- ber of seeks required while communicating arrays between main and auxiliary memory. Initial discussions concerned L— relation operator algorithms Which use main memory exclusively. Several algorithms of this type were created. These algorithms showed that, for nxn operands, union . Z . . . . requues at most n [om operations; dot—composrtmn requires at most 91 _———_——— 92 Zn3 - nZ lom operations; and reflexive dot-transitive closure requires at most 12(3) fom operations. For the class of totally ordered Tom's, an algorithm was given which showed that reflexive dot-transitive clo- sure can be performed in at most 3n(121) lom operations. Heretofore, fuzzy reflexive transitive closure was thought to require on the order of n3 log2 n 10m operations [T- 1, Z-3]. The central task undertaken in this research was the development of efficient algorithms for operating upon dimensionally-large L-rela— tions. First, recursive operator decompositions were derived, and each was shown to be efficient in the sense of requiring no more Zorn operations than were previously seen to be sufficient. Next, the re- cursive decompositions were converted to iterative decompositions which served as the basis for algorithms having adjustable main memory requirements. In addition to being efficient with respect to 10m opera- tions, the decomposition-based algorithms also exhibited a minimal number of seeks. It was shown that if pd x pd L-relations are stored in auxiliary memory and if computation is performed on d x d L- subrelations of these L-relations, then union requires at most 3p2 seeks; dot-composition requires at most 2p3 + p2 seeks; and reflexive dot-transitive closure requires at most on the order of ;p seeks. In general, the number of seeks required depends only on the dimension- ality, p, of the partitions. For the special case of J-relations, each MALGOL algorithm appearing in this thesis was transliterated to FORTRAN EXTENDED and implemented on the CDC 6500 computer. It is noteworthy that a direct translation from MALGOL to FORTRAN was possible in each cas e. This showed that the algorithms described in this thesis are CloSe relatives of machine algorithms. 93 An interesting and unexpected result emerged as a byproduct of this research. Specifically, it was observed that a k x k factored form of real matrix inverse can be derived using essentially the same tech— nique as was employed to validate 4. 4; except, in lieu of the 2 x 2 fac- tored form of reflexive dot-transitive closure (3. 10), the 2 x Z factored form of real matrix inverse is used (A. 1). Algorithm 4. 3 is easily adapted to the task of finding matrix inverses; one simply substitutes real matrix operator procedures, appropriately, in lieu of L- relation operator procedures. It should be noted, however, that the adapted version of Algorithm 4. 3 is valid only if certain principal minors of the given matrix are not zero. 6. 2. Future Research No attempt was made to demonstrate optimality of the algorithms presented; however, it is conjectured that the general algorithms which use main memory exclusively are optimal with respect to 10m opera- tions. It might be possible to verify this conjecture using the recursive decompositions. From such a demonstration, it would follow that the decomposition— based algorithms are optimal with respect to 20m opera- tions and seeks. On the other hand, if the general reflexive dot—transitive closure algorithm can be shown to be suboptimal, i. e. if a (*) operator algorithm can be found whose asymptotic bound on flom operations is less than na, where a < 3, then 3. 23 can be used in conjunction with this more efficient algorithm to effect a more efficient dot-composition algorithm. Con- versely, an improved dot-composition algorithm can be used in conjunc- tion with 3. 18—3. 21 to yield an improved reflexive dot—transitive closure algorithm. "r- y.‘ . 94 For the important class of tom's whose ordering is total, the reflexive dot-transitive closure decomposition appears to be suboptimal. On the order of Zn3 [om operations are implied by the decomposition equations (3. 18-3. 21); whereas on the order of%n3 10m operations are all that is necessary according to procedure transclosure2 (Algorithm 2. 5). It is conjectured that in this special case a more efficient de— composition exists, one which depends on L- relation operators other than union and dot-composition. The discovery of such a decomposition will probably emerge from graph-theoretic considerations. Much work remains to show how the iterative decomposition of reflexive dot-transitive closure can be simplified in special cases. There undoubtedly exist order relationships between the L- subrelations of a partition which, if active in a given L-relation, would remove the necessity to perform certain operations specified by the decomposition equations. Once these relationships are identified, tests for detecting them will be necessary. BIBLIOGRAPHY [A-ll [B-ll [B-fl [B-3] [B-4] [B-fl [B-H [C-ll [D-ll [F-ll [F-Zl [F-3] [G-I] [G-Z] BIB LIOGRA PHY Aczél, J. , Lectures on Functional Equations and Their Applica- tions, Academic Press, New York (1966). Bellman, R. E., Kalaba, R. and L. A. Zadeh, "Abstraction and pattern classification", RAND memorandum RM- 43 O7-PR, The RAND Corp. , Santa Monica, Calif. (1964). Bellman, R. E. and L. A. Zadeh, "Decision-making in a fuzzy environment", Management Science, Vol. 17, No. 4 (1970). Berztiss, A. T. , Data Structures Theory and Practice, Aca- demic Press, New York (1971). Birkhoff, (3., Lattice Theory, Am. Math. Soc. Colloq. Publ., Vol. 25, New York, Third Edition (1967). Blanché, R. , Axiomatics, Monographs in Modern Logic, Rout- 1edge and Kegan Paul, Ltd. , London (1962). Bottenbruch, H. , ”Structure and use of ALGOL 60", JACM, Vol. 9, No. 2 (1962). Chang, S. S. L. and L. A. Zadeh, "On fuzzy mapping and con- trol", IEEE Trans. Sys” ManL and Cyber., Vol. SMC-Z, No. 1 (1972). Dreyfus, S. E., "An appraisal of some shortest path algorithms", Operations Res., Vol. 17, No. 3, pp. 395-412 (1969). Fischer, M. J. and A. R. Meyer, "Boolean matrix multiplica- tion and transitive closure", Proc. Twelfth Annual IEEE Sym- posium on Switching and Automata Theory, Oct. 1971. Floyd, R. W., "Algorithm 97: shortest path", CACM, Vol. 5, p. 345 (1962). Frame, J. S. , ”Matrix operations and generalized inverses", IEEE Spectrum, Vol. 1, No. 3, pp. 208-220 (1964). Ginzburg, A. , Algebraic Theory of Automata, Academic Press, New York (1968). Goguen, J. A., "L—fuzzy sets", J. Math. Anal. Applic., Vol. 18, pp. 145—17 (1967). 95 96 [G-3] Gower, J. C. and G. J. S. Ross, "Minimal spanning trees and single linkage cluster analysis”, Applied Statistics, Vol. 18, pp. 54-64 (1969). [H- 1] Hu, T. C. , "A decomposition algorithm for shortest paths in a network", Operations Res., Vol. 16, pp. 91-102 (1968). [J- 1] Johnson, S. C., "Hierarchical clustering schemes", Psycho- metrika, Vol. 32, pp. 241-254 (1967). [M- 1] Munro, J. I. , "Some results in the study of algorithms", Tech. Rept. No. 32, Dept. Comp. Sci., University of Toronto (1971). [N- 1] Naur, P. , "Revised report on the algorithmic language ALGOL 60”, CACM, Vol. 6, pp. 1—17 (1963). [R-l] Robert, P. and J. Ferland, "Generalisation de 1'algorithme de Warshall”, RIRO, Vol. 2, No. 7, pp. 71-85 (1968). [S- l] Salomaa, A. , "Two complete axiom systems for the algebra of regular events", JACM, Vol. 13, pp. 158-169 (1966). [S- 2] Strassen, V. , “Gaussian elimination is not optimal", Nurner. Math., Vol. 13, pp. 354-356 (1969). [T- l] Tamura, S., Seihaku, H. and K. Tanaka, "Pattern classification based on fuzzy relations", IEEE Trans. Sys. , Man, and Cyb. , Vol. SMC—l, No. 1, pp. 61-66 (1971). [T- 2] Tarski, A. , "A lattice theoretical fixpoint theorem and its applications", Pacific J. Math., Vol. 5, pp. 285-309 (1955). [W— 1] Warshall, S. , "A theorem on Boolean matrices", JACM, Vol. 9, pp. 11-12 (1962). [W— 2] Wee, W. G. and K. S. Fu, "A formulation of fuzzy automata and its application as a model of learning systems", IEEE Trans. Sys. Sci. and Cyb., Vol. SSC—S, No. 3, pp. 215-223 (1969). [Y- 1] Yen, J. Y. , "Finding the lengths of all shortest pat s in n-node nonne ative distance complete networks using 1/2 n additions andn comparisons", JACM, Vol. 19, No. 3 (1972). [Y— 2] Yoeli, M. , "A note on a generalization of Boolean matrix theory", Amer. Math., Monthly, 68, pp. 552-557 (1961). [Z- 1] Zadeh, L. A. , “Fuzzy Sets", Information and Control, Vol. 8, pp. 338-353 (1965). [Z- 2] Zadeh, L. A. , "Toward a theory of fuzzy systems", in As ects of Network and System Theory, ed. R. E. Kalman, N. DeClaris; Holt, Rinehart and Winston, Inc. (1971). APPENDICES A PPENDICES APPENDIX A A DECOMPOSITION OF THE REAL MATRIX INVERSE OPERATOR In this appendix, (+) denotes real matrix sum; ( ) denotes real matrix product; and (- 1) denotes real matrix inverse. Let B denote a nonsingular, square matrix; and suppose that there is a 2 x 2 partition of B, denoted such that the submatrix B11 is nonsingular. Accordingly, B may be factored in terms of its partition as follows: I 1 ‘ I :0 B11 1 0 I 1311B12 B = —-——-——T——- ----1 ——————————————— —-1' —————— 4 -1 1 i ‘1 | B211311 1 I O i B22'13211311312 0 ' I . -1 . Now, furthermore, suppose that the submatrix (BZZ-BZlBllBlZ) is non—singular. Then using the properties: 1 -l -l 1) (MIMZ) = M2 M1 ; 11M”1 Iz-M 110‘1 110 ii) ~-:---» = ---+----; —---J,--- = ----- -'r--— 0: 1 o : 1 M . 1 —M1 1 . -1 -1 . M1: 0 MI I 0 mi) -—--f——-- = ----- Ir ----- , ' 1 -1 0 «M2 0 .112 where MI’MZ are nonsingular and M is arbitrary, it follows that B.1 can be expressed as 98 99 -1 I E $111312 B1] 5 o 1 1 o B - --------------- r ------------------- --------;r--- 0: I 0 i (13”22‘32113111312)1 “3211311 ; I (A. 1) Alternatively, consider that for each nonsingular matrix M, iv) MM'1 = 1. Accordingly, the partition of B satisfies B11] B12 (B-lhl ] (B-1)12 I 10 """ i'""' “""'J.""""‘ = "T" 3 B21 : Bzz (B- )21 (B—llzz 0 i I B11""11 + B12x21 = I (A. 2) Bllx12 + B12x22 : 0 (A.3) B21);11 + Bzzx21 = o (A.4) lex12 +Bzzxzz : I ' (A'S) where x.. = (B-1) 1 S i, j S 2. The objective is to solve this system 11 iJ' ’ of equations for the unknowns {xij }. In doing so, it will be tacitly under- stood that both B11 and (B —B B 1B 2) are nonsingular. 22 21 11 1 Using (iv) it is ascertained from A. 2 that -1 1 x11 ‘ B11“ B111312X 21 ”“6” Andfrom A.3, x — B1B A7) 12"111zx22' (- Using A. 6, A. 4 becomes -1 -1 B21(B11‘ B111312"21)+E"22x21 : 0' from which is obtained 100 -B B'lIBZ‘2)IB1'B , X 22 2111 11 21:‘(B using (iv). Substitution of A. 8 into A. 6 yields =B“II+BB B'IB X11 11 11 12(B22 I321 11 B12I1I321 Similarly, using A. 7, A. 5 becomes 'B21B11B12x22 I B22"22 = I ' from which is obtained _ 1 X ‘ (B 21311312)1 22 22 using (iv). And substitution of A. 10 into A. 7 yields _ 1 1 -1 12 ‘ ‘ I311I312IB 22‘ B21B1lB12) ° X In summary, —1 _ —1 —1 (B ’11 ‘ B11+I311I312III‘22 B21B11I312) B21B (B'I) =-B‘IB (B B B 1B ) 12 11 12 22 21 11 12 (B‘I) = —(B — B B‘IB ) IB B I 21 22 21 11 12 21 11 -1 _ 1 1 (B ’22 ‘ (322‘B21I311P’12) ' (A.8) -1 B11 . (A.9) (A. 10) (A. 11) 11 (A. 12) which agrees with the result obtained by carrying out the partitioned matrix multiplications in A. 1. APPENDIX B PROOF OF THEOREM 3.1 2 R and R l S k _<_ m < 00, shall denote members of LX ; more— k, over, F shall denote any p- ary operator obtainable by a finite successive application of the operators (+), ( ), (’1‘) to the p operands of F. Con- sider, for example, the ternary operator F(R1,R2,R3) = ((R1R3)I + R2R3 + R1) . Lemma B. 1 IX Q R implles IX g F(R) Proof: The proof is by the second principle of finite induction on the number n of L-relation operator applications necessary to obtain F. It is assumed that IX Q R. Basis. na : 1. Case 1. F(R) = R + R. By idempotency of (+), F(R) = R. Hence IX Q F(R). Case 2. F(R) : RR. By 1. 6 and Corollary 1.1 ii, IX : leX g RR : F(R). Case 3. F(R) = RI. Be Definition 1.11, 1 ; RI = F(R). X Induction step. na = n + 1. It is assumed that if F1(R) and FZ(R) are arbitrary unary operators, but which involve the application of n and 112 L- relation operators, 1 respectively, where 0 S n1, n2 5 n and 111 + 112 : n, then IX g R implies lOl 102 Case 1. F = Fl + F2. By idempotency of (+) and Corollary 1. l i, IX = IX + IX Q F1(R) + F2(R) = F(R). Case 2. F = F1F2' By 1. 6 and Corollary 1. 1 ii, IX = IXIX Q F1(R)F2(R) . = F1, where also 111 = n. By Definition 1. 11, F I ;[F1(R)]* = F(R). Theorem B. l IXCRk k:1,2,...,m implieslng(R1,...,R ) — m Proof: The proof is by a double induction on (i) the number na of L— relation operator applications necessary to obtain F and (ii) the num— ber no of operands of F. Basis. na =1: no. Lemma B. 1 constitutes the basis for the induction. Induction step. na 2 n + 1, no : m + 1. It is assumed, as the induction hypothesis on na, that if F1 and F are 2 arbitrary p— ary and q— ary operators, respectively, but which involve the application of L-relation operators n and 112 times, respectively, 1 where O S n1,n2 S n and n1+ nZ = n, then I g R for each k in X k {i1,... ,j1,...,jq}implies ,i p IXCF1(R. ,...,R. IXQF (R. ,...,R. ). Also it is assumed, as the induction hypothesis on no, that 1 s p, q S m and 103 {ikllSkSp}U{jk]15ks q} = {1,2,...,m+1} , where (kJ) is union in the crisp sense. Case 1. F = F1 + F2. By idempotency of (+) and Corollary 1. l i, IX = IX+LX gF1(Ril,...,Rip)+F2(Rj1,...,qu)= F(R1,...,Rm+1). Case 2. F = F1. By 1. 6 and Corollary 1. 1 ii, IX : IX].X g F1(Ril""’Rip)FZ(Rj1"°"qu) = F(R ..,R 1" m+l) ° Case 3. Suppose that G is an (m + 1)- ary operator of the form of either case 1 or 2, and furthermore suppose that G involves the application of L—relation operators n times. Let F = GI. By Definition 1. 11, IX 2 [G(R mm] .,R = F(Rl,...,R m+l) ' 1,“ Q.E.D. Lemma B. 2 >:< RQF(R) Case 1. F(RI'I) : RI + RI. By extensivity of (*) and idempotency of (+), R g R = RI +R* = F(RI). Case 2. F(RII) : RIRI. By extensivity of (*) and l. 9, R g RI = RIRI = F(RI). Case 3. F(RII) : (RII)*. By extensivity and idempotency of (*), R g RI = (R*)* = F(RI) . Induction step. na : n+1. It is assumed that if F1 and F2 are arbitrary unary operators, but which involve the application of L-relation operators 111 and n2 times, 104 reSpectively, where 0 5 111,112 5 n and n1 + n2 = n, then R g F1(R:I) and R g F2056"), Case 1. F = F1 + F2. By idempotency of (+) and Corollary 1. l i, >l< " :1 R = R+R c F1(R )+F2(R’") = F(R“). :9: >1: Case2. F=FF. ByLemInaB.l,I QR impliesI gF(R)and l 2 X X 1 IX g F2(R ). Hence, F1(R )F2(R ) = F1(R') + F2(R )+F1(R )F2(R ). And so by the same reasoning as in case 1, R g F1(R*) + F2(RI<) g F1(R"‘)FZ(R") = F(R’") . Case 3. F : F1 where also nlzn. By extensivity of (*), >k >:< >:< >: R c F1(R >g1F1(R )1 = F(R‘). Q. E. D. Theorem B. 2 m E k=1 Proof: Basis. n : l =n . a 0 Lemma B. 2 constitutes the basis for the induction. Induction step. na : n + 1, no : m+l. It is assumed, as the induction hypothesis on na, that if F1 and F2 are arbitrary p- ary and q— ary operators, respectively, but which involve the application of L—relation operators n1 and n2 times, respectively, where O S n1,n2 S n and 111 + n2 : n, then ZR. gr . k=1 1k 1 p 105 >:< :1: ER. QF (R. ,...,R. ). 2 11 Jq Also, it is assumed, as the induction hypothesis on no, that l S p,q 5 m and {ikllS ksmuuklls ks q} = {1.2....,m+ 1}. Case I. F = F1 + F2. By commutativity, associativity and idempotency of (+) as well as by Corollary 1. l i, m+l P >1< 2:: >1: >',< ZR = ER. +ZR. gF(R.,...,R.)+F(R.,.,R.) k:1 k k=1 1k k:1 3k I Ii Ip 2 J Jq : F(R1,.. °’Rm+1) ' Case 2. F = FIFZ‘ By theorem B. 1, IX g F1(Ri1,. . . ,Rip) and 1 c F (RT ,...,R'." ). Hence, 11 . Jq R.“ ,...,R’." )+ F (R l 1p 2 J1 \l b .,< P . . . RI: ) C F (RI: . . . Rik )F (RI: . . .. R ) . I 9 _. 1 1 ’ i j l 11 1 2 ‘Il j And so by the same reasoning as in case 1, m+1 * * >f< >',< ZR QF(R.,...,R. )+F(R.,...,R.) k=1 k 1 11 1P 2 J1 Iq . . (RI ,...,RI) = F(RI,...,RI 1 1p 2 jl Jq 1 m+l ) . Case 3. Suppose that G is an (m+ 1)- ary operator of the form of either case 1 or case 2, and furthermore suppose that G involves the applica- tion of L- relation operators n times. Let F = GI. Then reasoning as in case 1 or case 2 (depending upon the form of G) and using extensivity of (*1, F(R z Rk ; G(R£,...,R;n+l k=l ); [G(R1,-oo)Rm+1)] 106 Lemma B. 3 F(R) g R“ Proof: Basis. n = l a Case 1. F(R) : R + R. By idempotency of (+) and extensivity of (3‘), F(R) = R+R = R g RI. Case 2. F(R) 2 RR. By extensivity of (*) and Corollary 1. 1 ii, .1. fi‘ F(R) = RR g R*R* = R Case 3. F(R) = RI. Trivially, F(R) = R* g RI. Induction step. na : n + 1. It is assumed that if F1 and F2 are arbitrary unary operators, but which involve the application of L-relation operators I11 and n2 times, respectively, where 0 _<_ n1,nZ S n and n1 + nZ : n, then F1(R) g RI: and FZ(R) g R“. Case 1. F = F + F . By Corollary 1. l i and idempotency of (+), l 2 F(R) = F1(R) + F2(R) g RI +RI : R“. Case 2. F : FlFZ' By Corollary 1. 1 ii and l. 9, F(R) : F1(R)FZ(R) g R RI: = R Case 3. F : F1 where also n1 = 11 By monotonicity and idempotency of (.z), F(R) = (F1(R)) g(R) :R. . Theorem B. 3 NRynaRm)c( Proof: Basis. n =l:n . a o Lermna B. 3 constitutes the basis for the induction argument. Induction step. na : n + 1, no = m + 1. It is assumed, as the induction hypothesis on no, that if F1 and F2 are arbitrary p- ary and q— ary operators, respectively, but which involve the application of L—relation operators n and 112 times, respectively, 1 :R.) (ZRk). k:1 k k=1 k=1 3k k-l Hence, by idempotency of (+) and Corollary 1. l i, p :1: q >X< m+1 >3 (ERi)+(ZR.)Q(ZRk). kzl k k=1 Jk k:1 So, again by Corollary 1. 1 i, 108 EWR1,...,R. 1 m+1) = F (Ril""’Rip)+F1(Rj ,...,R. ) g ( z R Case 2. F : FIFZ' By monotonicity of (*), l. 9 and Corollary 1. 1 ii, F1R1,...,Rkn+l) = F1(Ril,...,Ri )F(Rj ,...,Rj ) p 1 q P ::< q >:: m+1 z}: C(ZR1)(ZR-)Q(2Rk). k:l k k:l Jk k:l Case 3. Suppose that G is an (m+ l)- ary operator of the form of case 1 or case 2, and furthermore suppose that G involves the application of L-relation operators n times. Let F = G*. Then by the same reason- ing as in case 1 or case 2 (depending upon the form of G), and by monotonicity and idempotency of (*), :1: m+l >l= I m+1 II: F(R1,.o~,Rm+1) : [G(R1"°.,Rm+l)] g ((kél Rk) ) : (kEIR-k) Q. 13.13 Now to prove Theorem 3. l, observe that by Theorem B. 2 and the monotonicity of (*), >}< m m >1: ::< >:: ( Z Bk) 2 (F(R1,...,R. )) k : 1 On the other hand, by Theorem B. 3, ,Rm) 2 F(R1,... G(Rl’ . .. So by monotonicity and idempotency of (*), m E R (F(RI :< 2:: m :1: I: :5 1"'°'R )) C ((ZRk)) =( k) . k:l k:l Therefore, using antisymmetry of the partial ordering g, z}: >}< m =1» (F(R1,...,Rm)) = (131111,) . .... pv4‘>"- v ' IMIC 11 ERS 111111111111111111111 1'1 ll 18 1111 11 Y LIBRARIES