LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAICN 510.84 cop 2. Digitized by the Internet Archive in 2013 http://archive.org/details/selectedproblems726cune U k'*^ uiUCDCS-R-75-726 7?IlZ* SELECTED PROBLEMS OF MINIMIZATION JH OF VARIABLE-VALUED LOGIC FORMULAS Ufi RARy 0F TH£ by Roland Phillipe Cuneo JUN 1 3 , 975 May 1975 UIUCDCS-R-75-726 SELECTED PROBLEMS OF MINIMIZATION OF VARIABLE -VALUED LOGIC FORMULAS by Roland Phlllipe Cuneo May 1975 Department of Computer Science University of Lllinois at Urbana- Champaign Urbana, Illinois 6l801 This work was supported in part by the Department of Computer Science and was submitted in partial fulfillment of the require- ments for the degree of Master of Science in Computer Science, 1975' Ill ACKNOWLEDGMENT I wish to express my thanks to my advisor, Professor R. S Michalski, who suggested the thesis topic and who has provided invaluable counsel. I also wish to thank my friends, especially Mary Brownlee, for their support and understanding. Special thanks go to Connie Slovak for her patience and efficient typing of this manuscript. IV PEEFACE In recent years there has been a growing interest in the use of logic for pattern recognition, machine learning and other related fields. Such names as Bibel [6], Michalski [l]-[5], Stoffel [7] > a nd others have been associated with research in the above-mentioned area. This thesis' is concerned with the implementation of algorithms for optimization of formulas of the variable -valued logic system VL . This thesis is also concerned with the use of an iterative process to obtain an optimal solution. By iterative process we mean a process by which a solution obtained at a given stage is used as the starting point to obtain a better solution at the next stage. Although this process might not produce an optimal solution, it is an efficient way to generate quasi-optimal or optimal solutions. The first two chapters contain the basic background material to make this thesis self-contained. The third chapter describes the optimization algorithms, and Chapter k shows how we implemented these algorithms. It also contains a user's guide. Finally we have in Chapter 5 two examples of how this program may be used. V TABLE OF CONTENTS Page 1 . INTRODUCTION TO VL AND GLD 1 2. SYNTHESIS OF COVERS 9 3 • MINIMIZATION ALGORITHMS Ik 5«1 Algorithm for Formula Minimization 1I4- 3 .2 Iterative Applications 18 k . IMPLEMENTATION OF THE ALGORITHMS 2k k . 1 Implementation 2k k.2 User's Guide 30 5 . EXAMPLES kk LIST OF REFERENCES 55 LIST OF FIGURES VI Figure 1.1 3-1 3-2 3-3 3-4 3-5 k.l 4.2 4.3 4.4 4-5 4.6 4-7 5-1 5.2 5-3 Page Generalized Logical Diagram (GLD) representing E(d 1 , d 2 , d^, d^) 8 The algorithm without generalization for VL mode 17 The algorithm without generalization for DC and IC mode.... 19 The algorithm with generalization for VL mode 20 The algorithm with generalization for DC mode 21 The algorithm with generalization for IC mode 22 Data structure for the representation of a complex 25 Initial binary bit string obtained to later represent a complex in the event space E(3,4, 5, 2,4) 25 Binary string and how variable and values are associated to it 26 GLD of Example 1 27 GLD of Example TI 28 The GLD diagram of Example 1 38 The GLD diagram of Example II k3 The GLD representation of the input covers in Example I.... 1+6 The GLD representation of the resulting output covers in Example I U7 Coloring map of U.S. A 51 1. INTRODUCTION TO VL ± AND GLD This first chapter is an introduction to the formal system used, which is called VL, • The VL system is a specific system which is a subset of a more general variable-valued logic (VL) system. The basic idea behind a VL system is that every VL formula and each of its variables may receive its own independent truth values, which are selected based on semantic and problem oriented considerations [l]. Truth values in a VL system differ as to the usual or standard binary value logic in that it doesn't only have true and false as its possible values. It may have more than two values if so desired, and each variable in a VL system doesn't have to have the same number of truth values since each variable in a VL system takes on its truth values from different domains. The concept of the VL system and the definition of VL, were first introduced [2] at the IFIP Working Conference on Graphic Languages, Vancouver, Canada, May 1972. The VL, system may be used in Pattern Recognition and Machine Learning since with its formulas one may describe an object or set of objects. Since the variables of the VL, system take on values from different domains one may have a variable taking on different values for different colors of an object and another variable may be taking different values for different predetermined sizes of objects, and so on, thus setting up a description of objects, people, and even concepts or conditions. Since one defines the domain from which a variable takes on its values, one may make the domains consist of as many or as few truth values as one considers necessary. Thus making the variable which takes its values from that domain very precise or less precise. For example, say one has a domain of length, it may consist of three values (small, medium, large) or it may be more precise by containing seven values (one foot, two feet, ..., seven feet) and one may notice that one can make it even more precise depending on what you are trying to describe and how much precision is required. From these domains one may set up a VL formula describing an object using the rules given later on. After having set up such a VL-, formula, we may use this formula to recognize the same or similar objects and reject dissimilar objects. The algorithm discussed in the following chapters is mainly interested in minimizing these descriptions, thus giving the most compact and simplest rules that will enable the machine to recognize an object just by checking if it satisfies the VL-. formula describing it, Following are the basic definitions and concepts of the VL., system as described in papers [l] and [3] • BASIC DEFINITION Definition of the VL System The VL system is an ordered quintuple where X -- is a finite non-empty (f.n.) set of input or independent variables whose domains, denoted by D., i=l, 2, 5> • • • r are non-empty sets where D, = (0,1,2, ...,L) ±=1,2,3,..- and d. is a natural number. Y -- is a f.n. set of output or independent variables, whose domains, denoted D, j=l,2,3, . .., are non-empty sets. S -- is a f.n. set of symbols, called connecting symbols. *F -- is a set of the formation rules which define wff formulas in the system (VL formulas) : 1. An element of D standing alone is a wff. 2. A form [L # R] is a wff, iff: #e{=,/,^,i0, Lg{X,V 1 }, Re{c,V 2 } X is a sequence of symbols x\ , iel, I c (1,2, ...,n], where x. is a variable x. or a form -|X. (also written i l i as x.), separated by symbol +. Or a name (when x denotes a variable whose values are such sequences) of such a sequence. c is a sequence of different non-negative integers ordered by the relation < (i.e. if c. < c., the c. i J i will appear before c. in the sequence) and separated by ', ' or ' : ' . c also may be a name of a sequence such as defined above. V ,V p are wffs or names of wf f s . 3. Forms (V), -,V, V 1 A V (also written V^), V 1 V Vg, V, V V and V, |V„ where V, V and V are wffs or names of wffs, are wffs. 1+ -iV is called the inverse of V. V-.Vp is called the product (or conjunction) of V and V . V V V is called the exception V from V (or V, except for V p ) V V V p is called the sum (or disjunction) of V, and Vp V- |v is called the separation of V and Vp R — is a set of interpretation rules which assign to any VL. formula V a value v(V)eD, depending on values of x ,...,x : 1. The value v(c) of an element c, ceD, is c, which is denoted: v(c) = c 2. [V if v(L) # v(R) ' v([L# R]) = { } otherwise where v(L), Le{X,V ), is v(V ), i.e., value of wff V,, if L is V,, otherwise is v(X), i.e., value of the sequence X. Assuming that X is a sequence of literals, X., iel, separated by ' + ', v(x) is defined as: v(x) = Z v(x ), iel where Z denotes arithmetic sum . <*> x. , if x. is x. (^ \ x' X i v(x.) = i -i . ^ a. -x. , if x. is -iX. x. denotes a value of variable x., x-eD. x x' i 1 v(R), Re{c,V }, is a sequence c, if R is c; otherwise v(V 2 ) v(L) # v(R), #€{=,£*,*}, is true if v(l) is in relation # with v(R) . If R is c, then: V(L) = c (v(L) 4 c) is true if v(L) is (is not) one of the integers in c, or is (is not) "between any pair of integers in c separated by ':' V(L) ^ c (v(L) > c) is true if V(L) is smaller than or equal to (greater than or equal to) every integer in c (in normal use of these relations c will consist of just one element) If v(L) # v(R), then the selector [L # R] is said to be satisfied. 3- v((V)) = v(V) v(-,V) = i -v(V) v(V 1 A V 2 ) = v(V x V 2 ) = min{v(V 1 ),v(V 2 )} v(V 1 V V ) = v(V x ), if v(V 2 ) = 0, otherwise v(V 1 V V 2 ) = max{v(V 1 ),v(V 2 )} '"v(V 1 ) if v(V 2 ) = v(V 1 |V 2 ) = / v(V 2 ) if v^) = ^ otherwise Parenthesis have their usual meaning, i.e. they denote a part of the formula to be evaluated as a whole. Operations are ordered from one with the highest to one with the lowest priority as follows: - AV v I- If there is more than one operation V, the priority goes from the leftmost one to the rightmost one unless it is changed by parentheses The interpretation rules R interpret VL, formulas as expressions of a function [l]: 12 n where x is the cartesian product and -> means 'mapping into 1 . The universe of events or event space is all the possible sequence of values of input variables of the set D, xD ft x... xD 1 2 n where D. = [0,1, .. .,<£.} for i=l, 2, . . .,n. Thus the event space is represented by E.(d ,d , . ..,d ) where d. is the cardinality of D. . The elements of the event space E are called events and represented by the vector (x-.,x_, ...,x ), where x. is a value of the variable x 1' 2 n i x., x.eD. . Each event has a unique number which specifies it which is called the number of the event e and denoted by 7(e), 1 k+1 where 7(e) = x + Z x. lid. ' n . _ is. . 1 k=n-l i=n to obtain the event given the number of the event one simply divides the number 7(e) first by d to obtain x which is the remainder of the 1 n n division, then divides the result by d -, to obtain x n which is the ' n-1 n-1 remainder and applies this algorithm successively until one obtains x.. • A geometrical model of the space E is introduced in paper [k] . Following are. the basic concepts and design of this planar geometric model of the event space E. Given an event space E such that E = (d_,d , . ..,d ). To make a visual representation of this event space one takes a rectangle and divide it into d horizontal section, then one divides each of these sections into d horizontal sections, and each of these sections one divide into d horizontal sections and one does this until one reaches d, , where cL is the last horizontal divisor and cL satisfies the condition that d • d • . . . • d, ^ cL ■ cL • . . . • d . Also k is the largest number for which the above equation is satisfied. Then one takes this rectangle and divide it into cL vertical sections each of which are to be divided into cL vertical sections which in turn are to be divided into d, ., vertical sections and so on until one reaches d which is the last vertical divisor. Then one assigns the vector (x , x , . . .,x,), x.e{0,l, . . .,d.} , i ^ k to the horizontal part of the rectangle or the rows of the rectangle, and assigns the vector (x, -, jX. , • • •> x ) ) x.e{0, 1, . . .,&.}, v < i ^ n to the vertical part of the rectangle or the columns of the rectangle [k] . A drawing of the above described Generalized Logic Diagram representing an event space is shown in Figure 1.1. As one can see, for a large event space this gets hard to do. o 7 / ^i-/ *-* : d,-/ <-' i i V I I i I I I t _ I V 1 1 1 1 1 1 1 1. o I * r . i-< x, Figure 1.1 Generalized Logical Diagram (GLD) representing E(dp dp,d,,d^) . 2. SYNTHESIS OF COVERS In this chapter we will introduce the concept of a cover of one event set against another event set. The concept of a cover is fundamental for the synthesis and minimization of VL, formulas. One may ask, "Why minimize a VL]_ formula?" There are several reasons. VL, formulas can be applied as descriptors of object classes. Therefore, the shorter and less expensive these VL formulas are the faster and cheaper it will be to recognize an object from an object class as described by the VL formula. For example, suppose one could find out if a person had a certain disease by either checking their blood chemistry or by performing an operation on that person. Obviously it would be less expensive and much quicker to check the person's blood chemistry and we would want this method of checking if the person had the certain disease as opposed to having him operated. Therefore we not only want to minimize a formula, we also want to specify the manner in which we would like it minimized or synthesized. That is why we have the optimal formula DVL, under functional A = [5] of formula V, where: 5 a-list: called attribute list is a vector a = (a.. , a , . . ., a„), where the a. I 7 2.' I 1 denote single or many-valued attributes used to characterize DVL, formula (e.g., number of terms, of selectors, total number of 10 variables Involved, the weight of each variable, etc.) T-list: called tolerance list, is a vector t = (T^Tg, ...jtp where g t ± £ 1, i=l, 2, ...,l and Tj_ is called tolerance for attribute a. . i The optimal forrniT. as are constructed by constructing a set of optimal covers of one event set against another event set. Thus in order to describe a process of optimizing VL, formulas we have to describe the concept of a cover CV(E, |e ) . Complexes are the building blocks of a cover. A complex is a VL formula which describes a set of events. A set £ c 2 fi is called universe of complexes, if it satisfies (i) Coverability criterion Ve£fi 3 C e£ , ■ e eC (ii) Separability criterion Ve-j^ e g €fi, 30^ C 2 e £, e ± eC ± and e g e C g Definition 1 : A cover CV(E, |e ), (where E, and E„ are any two disjoint subsets of ft), of sets E, against E is defined as a set of complexes, {C. } . -r such that ii el E i E u c i E a > c and l—i ^ a b b % d or a ^ c and c < b < d. The product is X. . 3« X. is not completely contained in X. which means either d > a > c and b > d or a < c and d < b < c the result is a. and X. respectively. Let C be the universe of complexes. Definition 2 : The root, vE (vE), of E is the set of all maximal complexes included in E n/e = {CeC |C c E and £ C ' c E, C c C ' } Definition 3 : The stars G(E, |e ) of E against E is defined as G(E 1 |E 2 ) = {C|C €n/I 2 and C n E 1 4 0} E is the negation of E . Definition k : The extension E — IE of the event set E against the event set E is defined as 12 E 1"~* E 2 = U t C l Ce Q( E 1 l E 2 )} MS -- is maxstar, which is the maximum number of complexes we want generated before trimming CS -- is cutstar, which, when we reach MS number of complexes, we trim down to CS number of best complexes according to A = . Given a cover CV, defined as CT = U C. where C. is a complex -L 1 i 1 1 r one can reduce the number of complexes in CV_ as follows if C, <= c , 1 k - 3' which means every literal of C k is equal to or contained in the literals of C . . Then we can omit C since it is completely contained in C . . To synthesize a cover CV-^ we use here a slightly modified version of the algorithm A q described in article [5]. Minimal and quasi- minimal covers are best and approximately best cover. Input E,E ,Cv!r,MS,CS,A M END ) Last value of M<1 is the quasi- minimal cover. Select a' complex C. from CV U Generate G(C 1 |e\cV^) with restriction Select L q from G(C ;L |e\CV u ) according to A M q = M^ U {L ( 1},CV= CV^IA e\cv = E\CV U (1/1} 13 The description of the algorithm is as follows. Given a cover CV-, and given the event space E, one takes a complex from the cover CV, and extend it into E\CV U , i.e., CV — IE\CV , thus generating a star for the complex chosen C*. The star is of course generated with the restrictions maxstar and cutstar. Then when one finishes generating the star, one picks the best complex that covers C. completely and does so according to the attribute A. Thus one has obtained the first complex L q of the quasi-minimal cover M^ of CV, . Now removing C. from CV, and any other complexes in CV, completely covered by L^, thus places L^ as part of E\CVn since one no longer cares to consider that complex. Then one repeats the above procedure until one has eliminated all the complexes of CV, and thus have IVr- as the quasi-minimal cover for CV. Ik 3- MINIMIZATION ALGORITHMS The first section of this chapter discusses the algorithm used in the program to minimize VL, formulas. The second section discusses iterative minimization. 3-1 Algorithm for Formula Minimization There are several different types and modes for minimal covers. When asking for a minimal cover one has to specify the kind of minimal cover one wants. For different problems one may require different ways of covering one 's classes. That is why there are two ways of minimizing a cover. One is without generalization, which means minimizing the cover but without extending its coverage or try to enlarge its range. Thus given a cover that covers n events one minimizes the cover without including any other event or events except for the n original events covered. The second method is with generalization, which means that if one can better minimize the cover given by including other events not included in the original n cover one should do so . Now for both of these types of covers there are three different modes of coverage. These are VL, DC, and IC . For the covers without generalization, DC and IC turn out to be the same thing. Following are the definitions of the different modes of coverage. VL: the formula is to be a DVL-, formula without any restriction (DVL are simple disjunctive VL formulas') . 15 DC: the formula is to "be a DVL formula with the property that the product of any two terms with different constants is zero ( 'disjoint covers ' ) IC: the formula is to be a DVL, formula with the property that the product of any two terms with different constants may be nonempty, but must not be satisfied by any event from the sets r (k=0, 1, . . .,$.) which are specified in the input data ('intersecting covers'). Now that the description on the type and modes of the minimal covers has been made, there are also two different types of complexes within the minimal cover. They are inclusive, i.e., the intersection of any two complexes may be non-empty, and exclusive, i.e., the intersection of any two complexes is empty. The algorithm A [l] shown in the previous chapter is for exclusive complexes, since we set E\CV U = E\CV U U L^. For inclusive complexes we simply leave E unchanged throughout the star generating process . Following are the algorithms used for obtaining the minimal cover with and without generalization and using the three different modes VL, DC, and IC . These algorithms were derived from a more general al oil thm constructed by Professor R. 3. Michalski. Before actually showing the algorithm used in the program, there are a few notations to be defined. CV^ -- is the i^h class or cover i th CV = {C,, Cp, ...,C } where C. is the i tn complex CV U = C. U r. U C, U . . . U C . CV U = C. UC, U... U C 12 3 n 12 n So 16 C, D C„ n CL n . . . fl C which after multiplication gives the following result CV U = C! U CI U ... U C f so one gets 12 m CV = [C^ C£, ..., (T) where C is the i th complex. CV -- is the negation of the i^" class or cover D . -- represents the cover against which we are covering CV. Q. -- is the quasi-minimal cover obtained for CV. i l Q(CV./d-. ) — is the algorithm A q by which one obtains the quasi- minimal cover CV. against D n - l ■ x i X (1 Y — is the intersection of X and Y X U Y -- is the union of X and Y X \ Y -- is all of X excluding Y. Given n classes one has the algorithm shown in Figure 3-1 for obtaining the minimal cover without generalization and in VL mode. The last class is not covered since in VL mode that last class is the default class. To familiarize the reader with the notation and flowchart of the algorithm, the following is a verbal description of the first . algorithm. First one negates the n"^ 1 class (which is the first calss of the input classes) to obtain D . Then one uses the algorithm A [l] to n . obtain the quasi-minimal cover Q which is the cover of CV n against D . st Next one intersects D with the negation of CV , (i-e., the n-1 class) to obtain D _ . Now one gets Q, - as the quasi-minimal cover of n-1 to ^n-l CV -, against D . One follows this general pattern until one reaches class two, i.e. CV 2 , which is the last class one obtains a quasi-minimal form for. That leaves CV. to be the default class as required by the VL mode . IT f START J > » D := CV n n \r \ : = « OT n ! V \ ' D _ := D fl CV\ , n-1 n n-1 i ' Vi : = « CT „.i/ D „-i) D 2 := D 3 n CV 2 Q2 := Q(CV 2 /D 2 ) :nd Figure 3.1 The algorithm without generalization for VL mode, 18 Figure 3-2 shows the algorithm to obtain the minimal cover of n classes without generalization and in DC mode which is the same for IC when there are no generalizations. If one wants a minimal cover with generalization and in VL mode for n classes, one has the algorithm shown in Figure 3.3. The last class is not covered since in VL mode that last class is the default class. Figure 3 .k shows the algorithm that will give the quasi- minimal cover of n classes with generalization and in DC mode. Figure 3.5 shows the last algorithm which is to obtain quasi-minimal covers for n classes in IC mode and with generalization. 3 -2 Iterative Applications Iterative minimization of VL-, formulas is a procedure by which after obtaining the quasi-minimal covers E.', 1=1,2, . ..,n from the n input classes E., i=l, 2, . . .,n one uses these quasi-minimal covers as one's input covers and goes through the minimization algorithm again to see if one obtains a better result. The program developed for this thesis has this above feature. The reason for having the iteration feature is to see if one can obtain an even more minimal cover than the first one obtained. The iteration feature was beyond the scope of this thesis. That is why only the simplest form of the iterative feature has been applied, which means that with a little research one might find a better way to use this iterative feature. For example, one may collect data as one first obtains the minimal covers. Such data s how many stars one generated to obtain each complex in the minimal cover will enable one 19 ( STAET J . 1 i D := CV n n w % ■■= <»< CT n / V >r C Vl := D n n C Vl \> D i := CT _ n-i n-1 \ t Vi := ^ c Vi /Vi) \ r D . := D . U D n-1 n-1 n ^ t C \.S := Vl n CT n-2 > > 1 ov-l^ d 2 n ^ V » D l : = ™1 s y Q x := QCCV-l /D 1 ) END Figure 3.2 The algorithm without generalization for DC and IC mode 20 ( START J W \ n := U CV, i=2 M *L" Q(CV! /D 1 ) w D 2 n := U CV. i=3 X >' Qg : = q(cv 2 /d 2 ) > ' 1 n D _ := U CV. n-1 . 1 x=n X 1 Vl : -« w n-l/ D n-l' END Figure 3*3 The algorithm with generalization for VL mode . 21 ( START Pi w D • = U CV. 1 i=2 i W G^ := Q(CV 1 /D 1 ) w 1 n D := (.U Q } U ( U CV.} ^ 1=1 i 1=3 x > f 02 := Q(CV 2 /D 2 ) > / Ak i.1 U { i=j+l D, := { U Q. } U ( U CV.} J i=i i i-iii Q. := Q(CV / D ) J 'J J n-1 D := U Q. n 1-1 x JJi 0^ := Q(CV n /D n ) KIM I) Figure 3 .k The algorithm with generalization for DC mode, 22 f START J \r D l n := .U CV. \CV n 1=1 1 N 1 >f \ := Q(CV 1 / D x ) v D 2 := U CV. \ CV i=l x d \' % := Q(CV 2 /D 2 ) 4c n u cv, \cv i=l 1 J Q, Q(cv^ /dj) 1 D n := U CV \CV i=l x n N » ^ := Q(CV /D ) END Figure 3-5 The algorithm with generalization for IC mode. to start with the complex that generated the fewest stars so as to speed up the process of picking the best one. This type of information and other information may be used to improve the iteration feature. 2k k. IMPLEMENTATION OF THE ALGORITHMS In the first section of this chapter discusses the method in which the algorithm described in the previous chapter for VL, formula minimization was implemented, the data structure for the program and the way different VL operations were performed. The second section is a guide on how to use the program, how to specify the input and how to interpret the output from the program. k.l Implementation Each complex is stored as a sequence of binary bits, i.e., as a binary string, whose length is the sum of the levels of all the variables in the event space, thus having L.B.S. (length of binary string) . The identical representation for complexes as was used in the program AQVAL/l (AQ7) is used here. n L.B.S. = 2 d. i=l X where and E = D.. X D x . . • X D 12 n d. = c(D.) 1 v i 7 Thus obtaining the following data structure where BPTR is the back pointer (i.e., the pointer which points to the following complex) and FPTR is the front pointer (i.e., the pointer which points to the previous complex) and their value is NULL if there are no complexes to point to. 25 To represent a cover consisting of more than one complex one simply links several of the structures shown in Figure k.l using FPTR and BPTR to know which complexes belong to a certain cover or class . BINARY STRING REPRESENTING THE COMPLEX FPTR L.B.S BPTR Figure lf.1 Data structure for the representation of a complex . Following is an example of exactly how a complex is represented with a binary string. Given the event space E = (3,k,5 } 2,k) we get L.B.S. = l8 so we obtain the following binary string of eighteen bits in length. The first variable is represented by the first three bits in Figure h .2 which represents the values zero, one and two respectively. oooooooooooooooooo Figure k.2 Initial binary bit string obtained to later represent a complex in the event space E(3A 5,2,10- 26 So if the first variable is equal to one (i.e., [xl=l]) one places a one for the "bit that represents the value one (i.e., 010). The second variable is represented by the next four bits, the next five bits represent the third variable, the two bits after that represent the fourth variable and the fifth variable is represented by the last four bits. Figure k .3 shows which bits are assigned to which variable and the value each bit represents for its variable. xl x2 x3 xk x5 'o o o"o o o o 600 o o^ '0000 01201230123^01012 3 Figure k.3 Binary bit string and how variable and values are associated to it. A '1' is placed wherever that value is associated with the variable. '1's'are placed for all the values of a variable if that variable is not in a complex. Thus obtaining the following complex [xl=0,2][x3=l,2,3][x^=l][x5=0] represented by the following binary string xl x2 x3 xk- x5 101 111? 01110 'SJ'lOOO* 27 where one has all ones for x2 since x2 is not in the complex which means that the complex is true for all values of x2 given the above conditions for the other four variables. There are really only three essential operations used. They are multiplication of complexes (also known as the intersection of complexes), the negation of complexes, and the containment of a complex (i.e., the operation to check whether a complex is the proper subset of another complex) . The operation multiplication or intersection of two complexes is simply done by a bit by bit AND of the binary bit strings representing these complexes. Example I ; Consider the event space E = (2, 3>2) and the complexes L-j_ = {xl=0}{x3=l} and L p = {xl=0}(x2=2} . Multiplying them one obtains the complex L* = (xl=0) (x2=2) (x3=l) as shown in Figure k-.k. Figure k.k CLD of Example 1 28 The "binary bit string representation of L, and L„ are 1011101 and 1000111 respectively. When "by ANDing these two binary strings, one obtains 1000101 which is the binary bit string representation complex Lz . Since multiplication is the intersection of complexes, it might happen that the intersection is empty. When this happens, one finds that all the values of one or more variables have a zero in the binary string. Example II shows this case. Example II : Given the same event space as in the last example and our two complexes being L, = {xl=l}{x3=0) and L ? = {xl=0}{x2=2} one notices that the intersection is the empty set as shown in Figure k.5> Z-0 Figure k.5 GLD of Example II The binary string for L and L are 0111110 and 1000111 respectively and if one bit by bit AND's these two strings one gets 0000110. As can be seen, there are no values for xl so one gets the empty set as one's answer. 29 When given two complexes L- and L p , if one wants to check if L. is a proper subset of L one simply applies a bit by bit AND of the two binary strings representing L-, and L p , and check if the binary string representing L, is the same as the binary string of the result of L-, AND L p . If it is, then L is a proper subset of L p ; otherwise it is not. Last but not least is the manner in which a complex is negated. Suppose the event space is E = (2,^,3*3) and let the complex to be negated be L, = {xl=0} {x2=l,3} 1x^=2} the negation of L is the set of three complexes L v L ' V L' which are {xl=l}, {x2=0, 2} and [xk=0, 1} respectively. When negating a complex one creates a set of binary strings, one for each variable in the complex to be negated, that does not have all ones in the binary string of the complex to be negated. These binary strings contain all ones except where the variables they are matched up with have ones in the binary string of the complex being negated. Example III ; The binary string of L is 100101111001. So, for the negation of L, one gets three binary strings since x3 has all ones in the binary string representing L, . The binary string matched up or associated with xl is 011111111111, the binary string for x2 is 111010111111, and for x'l we have 111111111110. As you see, each variable in its binary string has a zero where there was a one for it in the binary string of the complex to be negated. Now for a simplified overfiew of how one obtains the minimal cover. 30 Take the first algorithm given in Chapter 3 of this thesis. Given a cover CV = L n v L_. V • • • V L where L. , 12 n i/ i=l,2j . ..,n are complexes, we negate it to obtain CV U which is the same as L • L p ■ L-, • . . . • L using a routine that will negate any complex using the method explained above. Then multiplying these complexes using the method shown for multiplication of complexes, and absorbing them using the containment operation given earlier so as not to have any redundant complexes. After these operations, one comes out with CV = L' V Lp V ... V L' where L.% i=l, 2, ...,m are complexes Now by simply using the star generation for CV against CV the quasi- minimal form for the cover CV is obtained. k.2 User's Guide AQ9 is a PL/1 implementation of an algorithm for the minimization of VL formulas. This program will synthesize quasi- optimal formulas given in DVL, form. One may specify for the quasi- minimal complexes to be inclusive or exclusive of each other. One may also ask for dependent or independent covers. There are three cover modes which are VL, DC and IC. They are described below. Program Input The format for the input to AQ9 is as follows: 1. The variables LTRACE, QTEACE, GNNC, ITEPA, GONG, INOEEX, MODE, MAXSTR, and CUTSTR are read in Pb/l DATA format. Default values are given within parentheses. LTRACE( 'O'B) : if M'B is specified a full trace of the synthesis of covers will be printed. This feature is for debugging purposes. (Users should not use it.) QTEACE('O'B) GNNC(200) : ITERA(i; GONG(GN) : INOREX(EX) MODE(VL) : 31 if 'l'B is specified a quick (short) trace of the synthesis of covers will be printed. Users should not use this unless necessary. this is an array parameter which should be big if the event space is large. this specifies the number of iterations wanted. Where after the first iteration one takes the output and uses it as their input for the subsequent iteration in an attempt to improve our result. this is the type of cover to be generated. GN means a cover without generalization, and GE is a cover with generalization. specifies type of complex one wants EX for exclusive (i.e., any two complexes in the same class when intersected give the empty set) and IN for inclusive (i.e., any two complexes in the same class when intersected may be non-empty) . there are three modes. They are: VL the formula is to be a DVL* formula without any restrictions (i.e., any two complexes in the same class when intersected gives the empty set) . DC the formula is to be a DVL, formula with the property that the product of any two terms with different constants is ('disjoint covers'). where DVL-^ formulas are disjunctive simple VL-^ formulas. 32 IC the formula is to be a DVL, formula with the property that the product of any two terms with different constants may be non-empty, but must not be satisfied by any event from sets F^ (k=0, 1, .. .,$.) which are specified in the input data ('intersecting covers'). MAXSTR, CUTSTR(50000 each) : if an intermediate star contains more than MAXSTR complexes, it is cut to CUTSTR best complexes (according to the attributes specified) . 2. The number of variables and the number of classes, which are read in PL/l LIST format. 3. The variables NCRIT, CLIST, and TLIST are read in PL/l LIST format. NCRIT: specifies the number of attributes. CLIST: is the list of attributes. TLIST: is the list of tolerance of each attribute. So far k attributes are available to select from. ATTRIBUTE#1. The number of complexes completely covered by the newly selected complex (the more the better). ATTRIBUTE#2. The number of variables in the newly selected complex (the less the better) . ATTRIBUTE^. The number of states (i.e., levels) for each variable in the newly selected complex (the more the better) . ATTRIBUTE^. The sum of the weight of all the variables in the newly selected complex (the less the better) . For attribute^ one has to specify the weight for each variable. This is read in PL/l LIST format. 33 k. Specifies the number of states (i.e., levels) of the variables, (the event space). This is read in Pl/l LIST format. 5. The variable TYPE is read in Pl/l DATA format. Default value is given within parentheses. TYPE (EVENTS) : this specifies the type of data to be given. TYPE = 'BOTH'; implies events and complexes in that order. TYPE =' COMPLEXES ' , implies complexes only and TYPE = 'EVENTS', implies events only. This is done for each class. 6a. If TYPE is specified as BOTH, then the next piece of data is the number of events and the number of events to be converted to complexes. These are read in PL/l LIST format. Since this program is mainly oriented to minimize complexes, number of events to be converted to complexes, allows one to specify how many events are to be actually considered as complexes in this cover. The program will check if any of the events are already included in the complexes one has given. Then it will check how many events remain, if that is larger than the number of events to be converted to complexes, it will not convert any of the events into complexes, otherwise it will convert them all. After one enters the events, which are read in PL/l LIST format, then one inputs the number of complexes followed by the number of selectors for each complex. This is also read in PL/l LIST format, and then one inputs one's complexes. 6b. If TYPE is specified as COMPLEXES, then one inputs the number of complexes followed by the number of selectors for each complex. This is read in PL/l LIST format. All this is then followed by your complexes. 3h 6c. If TYPE is unspecified or specified as EVENTS, then one just number of events read in PL/l LIST format, followed by the events also read in PL/l LIST format. JCL for running AQ9 /"^ID (id number and name) /*ID ( codeword) /*TD (time, lines, ioreq, region, etc.) //JOBLIB DD DSN = USER.P2123 -COMEVE, DISP = SHR // EXEC PR0GPL1X, PROG = AQ9, REGION = 250K //GO. SYS IN DD * i i i i (Program input) ■ I I /■* (last symbol) Following are two examples of the format in which the input data should be and the type of output you obtain from it. Restrictions The main restriction is the size of the event space in that, the larger the event space the longer it takes. There are two things that make the event space large: 1. the number of variables 2. the cardinality of the variables. 35 Due to lack of symbols, [ ] are replaced by ( ) Sample Input EXAMPLE #1 Actual Input (1) LTRACE='0'B QTRACE='0'B GNEC=300 ITERA=1 GONG='GE' INOREX='IN' MODE='VL' MAXSTR=3 CUTSTR=1 ; (2) 2 2 (3) 1 1 0.00 (it-) 6 6 (5) TYPE= ' COMPLEX ' ; (6b) 6 2 2 2 2 2 2 (X1=0 (X2=0 (Xl=l (X2=l (Xl=2 (X2=2 (Xl=3 (X2=3 (Xl=4 (X2=lf Information about Input (number of variables and number of classes) (number of attributes and attribute number) (tolerance of above attribute number) (number of states of the above variables) (number of complexes followed by the number of selectors for each complex) (first complex with two selectors) ( second complex with two selectors) (third complex with two selectors) (fourth complex with two selectors) (fifth complex with two selectors) 36 (Xl=5) ^ (X2=5) j (5) TYPE=' COMPLEX'; (6b) 6 2 2 2 2 2 2 (X1=0 (X2=l (Xl=l (X2=0 (Xl=2 (X2=0 (Xl=3 (X2=l {Xl=k (X2=l (xi=5 (X2=l 2) 2,5,^,5) 1,3 A) 2^) 2,3,5) *0 (sixth complex with two selectors) (number of complexes followed by the number of selectors for each complex) (first complex with two selectors) (second complex with two selectors) (third complex with two selectors) (fourth complex with two selectors) (fifth complex with two selectors) (sixth complex with two selectors) With this input you obtain the output shown on the following page. Sample Output EXAMPLE #1 37 Actual Output NUMBER OF VARIABLES^ 2 NUMBER OF CLASSES 2 MODE IS VL MAXSTAR IS 3 CUTSTAR IS 1 CLIST= 1 TLIST= 0.00 NUMBER OF LEVELS FOR EACH VARIABLE : 6 6 Information about Output THE NUMBER OF COMPLEXES FOR CLASS ARE 6 THE COMPLEXES OF E(l) ARE: (X1=0)(X2=0) V (Xl=l) :xi=5)(X2=0,5) (X1=0)(X2=1,2) (X1=1)(X2=0,2,3,^5) (X1=2)(X2=0,1,3A) (Xl=3)(X 2=1,2, k) (X1=^)(X2=1,2,3,5) (X1=5)(X2=5) -- class zero 1 -- class one ' Figure k.6 The GLD diagram of Example I, Sample Input EXAMPLE #2 39 (2) Actual Input LTRACE='0'B QTRACE='0'B GOTC=300 ITEBA=1 GONG-'GN' INOREX='EX' MODE='DC MAXSTR=3 CUTSTR=1 ; 2 2 Information a"bout Input (3) 1 l 0.00 (10 6 6 (5) TYPE= ' BOTH ' ; (Ga) 8 5 k 5 2 5 3 5 2 1+ 5 3 5 2 2 2 (number of variables and number of classes) (number of attributes and attribute number) (tolerance of above attribute number) (number of states of the above variables) (number of events and number of events to be converted to complexes) (the events) (number of complexes followed by the number of selectors for each complex) ko I (first complex with (X2=0 5) J tw ° selectors ) 1 (second complex with (X2=0 2 3) J tw ° selectors ) (5) TYPE=' EVENTS'; (6a) 6 (number of events) 1 1 2 2 (the events) 3 3 h k 5 5 The following pages contain the output to the above input, Sample Output EXAMPLE #2 1+1 Actual Output NUMBER OF VARIABLE S= 2 NUMBER OF CLASSES 2 MODE IS DC MAXSTAR IS 3 CUTSTAR IS I CLIST= 1 TLIST= 0.00 NUMBER OF LEVELS FOR EACH VARIABLE 6 6 Information about Output THERE ARE 8 EVENTS FOR CLASS THE NUMBER OF COMPLEXES FOR CLASS THE NUMBER OF EVENTS IS 5 THE COMPLEXES OF E(l) ARE: (X1=3)(X2=0,5) V (X1=5)(X2=0,2,3) V 1 ARE 2 (these are the input complexes entered for the (X1=0)(X2=10 V (X1=2)(X2=5) V first class) (X1=0)(X2=3) V (Xl=10 (X2=0) v (X1=0)(X2=5) THERE ARE 6 EVENTS FOR CLASS THE COMPLEXES OF E(0) ARE: (X1=0)(X2=0) V (X1=1)(X2=1) v (X1=2)(X2=2) V (X1=3)(X2=3) V (X1=U)(X2=^) v (xi=5)(X2=5) ^■-^ITERATION #1*** THE COMPLEXES OF Q(l) ARE: (Xl=3)(X2=0,5) V (X1=5)(X2=0,2,3) V (X1=0)(X2=3,^,5) V (X1=2)(X2=5) V (X1=10(X2=0) (these are the input complexes entered for the second class) (this is the output giving the quasi-minimal cover of the first class after one iteration in DC mode) k2 THE COMPLEXES OF D(l) ARE: (Xl=l) V (XL=2)(X2=0, 1,2,3,^) V (X1=J0(X2=1,2,3A,5) V (X1=3)(X2=1,2,3,*0 V (X1=5)(X2=1,4,5) V (X1=0)(X2=0,1,2) THE COMPLEXES OF Q(O) ARE: (X1=1)(X2=1) v (X1=2)(X2=2) v (X1=*0 (X2=4) V (X1=3)(X2=3) V (X1=5)(X2=5) V (X1=0) (X2=0) THE COMPLEXES OF D(O) ARE: (XL=1)(X2=0,2,3,^,5-) V (X1=2)(X2=0,1, 3,k,5) V (X1=J4-)(X2=0,1,2,3,5) V (X1=3)(X2=0,1,2>,5) V (KL=5)(X2=0 ; 1,2,3, 1 »-) V (X1=0)(X2=1,2,3,^5) (this is the output giving the qua si -minimal cover of the negation of the first class) (this is the output giving the quasi-minimal cover of the second class after one iteration in DC mode) (this is the output giving the qua si -minimal cover of the negation of the second class) *****NORMAL TERMINATION**-*** EXECUTION TIME = 1,304- centi seconds EXAMPLE #2 >J-3 X 1 1 2 2 3 3 ij- 2 3 4- (X1=5)(X2=0,2,3) o m ~m o o 3 o> 05 O i o 2 © 2 5 (Xl=3)(X2=0,5) k k 5 5 3 * 5 X 5 2 5 3 1 -- class one -- class zero Figure. ^.7 The GLD diagram of Example II, kk 5 . EXAMPLES This chapter consists of two examples to demonstrate the ability and use of the program discussed in the previous chapters. example' #1 Here are three classes and their descriptions are as follows These classes are from the event space: E = (3,h, 4,3)- where where where Class one = L V L v L , L L1 = Ul=l, 2} 1x3=2} 1x4=0,1} L 12 = (xl=l, 2} 1x2=0,1,2} 1x3=2} {x4==l, 2} L 15 = (xl=l, 2} 1x2=2,-3} 1x3=2} Class two = L 21 V L 22 V L L 21 = (xl=0} 1x2=0,1} 1x3=1, 3} L 22 = (xl=0}{x3=0,2} . L 23 = (xl=0}(x2=l,2,3} Class three = L,, V L^ v L„ v L^i. V L-,.- 31 32 33 34 35 L,_ = 1x1=2} Ix2=0}[x3=0} 31 L 32 = 1x1=2} 1x2=1} 1x3=0} L„ = 1x1=2} 1x2=2} 1x3=0} L^ = 1x1=2} 1x2=3} U3=0} L 35 = {xl=2} {x3=0} 1x4=1} ^5 Figure 5*1 gives a GLD representation of these above three classes. As one can see, the complexes within a class are redundant in that they almost all intersect each other. This data was run through the minimization program. The type of cover was with generalizations and the mode was disjoint covers (DC) . The result obtained was as follows: Class one = L' = [xl=l,2} [x3=l,2,3} Class two = L* = {xl=0} Class three = L' = (xl=l,2) (x3=0] The result is shown in the form of a GLD in Figure 5-2. As one may have noticed, class one was expanded and simplified in that only two variables were sufficient to describe or cover it. Class two was simplified so as to only require one variable to describe it. It was not expanded since if it had been its descriptor, it would have been more complicated. Class three was simplified and expanded. EXAMPLE #2 The problem described in this example was suggested by R. S. Michalski. The problem is to color the map of the United States in such a manner so as not to have bordering states of the same color (i.e., two states next to each other are not supposed to be of the same color) . States that were kitty- cornered were allowed to be the same color. The whole map was not colored all at once since the event space would be rather large and thus take a lot of computer time and money. 'Iherefore, the map was colored in parts of about ten to eleven states at a time, which took anywhere from ten to fifty seconds to execute. The type of cover asked for was with generalization and the mode was VL. The maxstar was three and cut star was one. There E(3AA3) 1+6 X- class. 3 L *4 C«/H/»£t?X o/-~ .* iAc L/»SS Figure 5.1 The GLD representation of the input covers in Example 1. E(3A^,3) ^7 \ \ L n o r " i i I o 2 1 l 1 3 T 1 *- - 1 ' 2 3 / ° L ?> / ^ 2 f 3 i o i f 2 o / 2 / a. o / z x, o 2 3 L„ X, class 3 2 J *.ss Figure 5.2 The GLD representation of the resulting output covers in Example I . )+8 are two classes, the first one has the states to be colored and the second one has all the states that border on each state of the first class and it does not include any state that is not in the first class. The results obtained are several groups (between three or four) of states that can be the same color. It took seven runs to color all of the map of the U.S.A. The reason for this was that one could not just take five sets of ten states and color them since one could get two states that border on each other being the same color because they were in separate sets. So, one had to color one set at a time. Therefore, the next set would contain some states from the previous sets. It would contain all the states that were already colored that bordered on the states to be colored. Figure 5-3 (a) through (g) show this process of coloring the map of the U.S.A., with Figure 5 -3(g) being the end result. In this example, one has two variables xl and x2, denoting the state and the bordering states that are not supposed to be the same color. For the first run one has -- Washington 5 — Arizona 1 — Oregon 6 -- Montana 2 -- California 7 — Wyoming 3 — Idaho 8 -- Utah k. — Nevada 9 — Colorado The two classes were [xl=0][x2=0] V [xl=l][x2=l] V ... V [xl=9][x2=9] and [xl=0][x2=l,3] V [xl=l][x2=0, 2,3,^1 V [xl=2][x2=l,^ 5l V [xl=3][x2=0,l, ^,6,7, 8] v [xl=l*][x2=l,2,3,5,8] V [xl=5][x2=2,^,8] v [xl=6][x2=3,7] V [xl=7][x2=3,6,8,9] v [xl=8][x2=3A5,7,9l V [xl=9][x2=7,8] h9 The first class specifies the states to "be colored and the second class specifies which of these states to be colored cannot he the same color. The program was run in VL mode with generalization. The result obtained was [xl=0,2,6,8][x2=0,2,6,8] V [xl=l,5,Tl[x2=l,5,T3 V [xl=3,9][x2=2,3,9l V [xl=ij.][x2*0,^6,7,9] This means that states 0,2,6, and 8 can be the same color, say color one. States 1, 5, and 7 are color two. Color three is for states 3 and 9* and state four will be color four (as shown in Figure 5.3(a) . The next set of states was as follows -- Montana 5 -- Nebraska 1 -- Wyoming 6 — Kansas 2 -- Colorado 7 -- Minnesota 3 -- North Dakota 8 -- Iowa k — South Dakota 9 -- Missouri The two classes are as follows and they specify the same thing as the last time [xl=0][x2=0] v [xl=l][x2=l] v ... V [xl=9][x2=9] and [xl=0][x2=l, 2, 3 Al V [xl=l][x2=0,2,^,5] V [xl=2] [x2=0, 1, 5, 6] v [xl=3l[x2=0,4,7] v [xl=)+][x2=o,l,3,5,7,8] v [xl=5][x2=l,2,^,6, 8, 9] V [xl=6][x2=2,5,9l V [xl=7][x2=3,^,8] v [xl=8][x2=^, 5,7, 9l V [xl=9][x2=5,6,8] It was run the same way as the last one and the result was as follows [xl=0,5,7][x2=0,5,7l v [xi=i,3,6,8][x2=i,3,6,8] v [xl=2,4,9][x2=2,^,9l 50 As one can see, three states were used that were already colored so as to know which of the four colors used this set of states should be colored. One gets that states 0, 5, and 7 get color one since Montana was color one in the first run. States 1, 3, 6, and 8 get color two since Wyoming was color two and states 2, k f and 9 get color three since Colorado was color three. So the result obtained is as shown in Figure 5 '3(b). One follows this strategy until one has colored all the states. The progress is shown on Figure 5-3 (a) -(g), as each set was colored until the whole map was colored. 51 lid ioi" 1*1 sv -U i\ 90' 65 i ^rv\ • ---.... J.iv--.: .yv- •7 V > ...I ..-••1'. Ki> -^ i I M zz % r v x *""*»- ? ~N 100' - «/«.••<•-'...• [ff !k Figure 5o( a ) Coloring map of U.S.A. '•..y*5 fr J. r %$ ?&i 3 C/ U.2.J ~ v . S\ i m \\ t r Jt A \ ■ \ I »•<»' — W .'1 y %"■> Figure 5 '3(b) (continued) Coloring map of U.S.A. 52 Figure 5.3(c) Coloring map of U.S.A. Figure 5.3(d) (continued) Coloring map of U.S.A. 53 Figure 5.3(e) Coloring map of U.S.A. Figure 5.3(f) (continued) Coloring map of U.S.A. % Figure 5 -3(g) Coloring map of U.S.A. 55 LIST OF REFERENCES [1] Michalski, R. S., "VARIABLE -VALUED LOGIC : System VL]_, " Proceedings of the 197^- International Symposium on Multiple-Valued Logic , West Virginia University, Morgantown, West Virginia, May 29-31* 19-jk. [2] Michalski, R. S., "A Variable -Valued Logic System as Applied to Picture Description and Recognition," GRAPHIC LANGUAGES, Proceedings of the IFIP Working Conference on Graphic Languages , Vancouver, Canada, May 1972. [3] Michalski, R. S.,- "AQVAL/l — Computer Implementation of a Variable- Valued Logic System and the Application to Pattern Recognition, " Proceedings of the First International Joint Conference on Pattern Recognition , Washington, D.C., October 30-November 1, 1973? pp. 3-17- [k] Michalski, R. S., "A Geometrical Model for the Synthesis of Interval Covers," Report No. k6l, Department of Computer Science, University of Illinois, Urbana, Illinois, June 2h, 1971. [5] Michalski, R. S., "Synthesis of Optimal and Quasi-Optimal Variable-Valued Logic Formulas, " submitted for presentation at the 5^h international Symposium on Multiple-Valued Logic, Bloomington, Indiana, May 13-l6, 1975- [6] Bibel, W., "An Approach to a Systematic Theorem Proving Procedure in First Order Logic," May 13, 1975. [7l Stoffel, W., "The Theory of Prime Events Data Analyses for Sample Vectors with Inherently Discrete Variables." [8] Larson, J. and R. S. Michalski, "AQVAL/l: User's Guide and Program Description, " Department of Computer Science, University of Illinois, April 1975 . 3LI0GRAPHIC DATA EET 1. Report No. UIUCDCS-R-75-726 3. Recipient's Accession No. JTitle and Subtitle SELECTED PROBLEMS OF MINIMIZATION OF VARIABLE -VALUED LOGIC FORMULAS 5. Report Date May, 1975 6. \uthor(s) Roland Philippe Cuneo 8. Performing Organization Rept. No. I Performing Organization Name and Address Department of Computer Science University of Illinois at Urbana- Champaign Urbana, Illinois 6l801 10. Project/Task/Work Unit No. 1.1. Contract /Grant No. Sponsoring Organization Name and Address Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 13. Type of Report & Period Covered 14. Supplementary Notes Abstracts Algorithms for the minimization of variable-valued logic formulas are described. The method of implementation of these algorithms in a PL/l program AQ9 is given along with a user's guide and two examples. Also included is the basic definition of the variable-valued logic system VL-, • Key Words and Document Analysis. 17o. Descriptors 13 Identifiers /Open-Ended Terms 1 ( OSA II Field/Group " Availability Statement 1 <* NTIS-'iB I 10- 701 19. Security Class (This Report ) UNCLASSIFIED 20. Security ('Mass (Tlii Page UNCLASSIFIED 21. No. of Pages 22. Price USCOMM-DC 40329-P71 m 2 4»?5 rs- m a. UJ CO