APPROXIl\IIATING THE RANK OF A HOMOMORPHISM USING A PROLOG BASED SYSTEM by Richard Kenneth Little B.Sc .. The University of Northern British Columbia, 1996 THESIS SUBl\liTTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF ARTS ll1 INTERDISCIPLINARY STUDIES c Richard Kenneth Little, 2000 THE UNIVERSITY OF NORTHERN BRITISH COLUMBIA May 2000 All rights reserved. This work may not be reproduced in whole or in part, by photocopy or other means , without the permission of the a11thor. UNIVERSITY OF NORTHERN BRITISH COLUMBIA LIBRARY Prince George, BC Abstract A system of Prolog based programs for the purpose of approximating the rank of algebraic operations of finite nnary algebras is presented. The rank function is a measure of finite algebras and their algebraic operations. Rank is a recursive function used in universal algebra and was first introduced as a tool for proving strong dualizability. Logic programming. particularly Prolog, is commonly used in natural language processing, an area of study devoted to the nse of computers to understand human (natural) languages. One goal of this thesis is to explore a relationship between the fields of Mathematics and Computer Science through the application of logic programming techniques on structures from uuiversal algebra. This thesis is motivated by the idea that when universal algebra is viewed as a laugnage, the ideas of natural language processing can be used to create a computer system which approximates rank. The outcome of the research is a computational model that computes the Kth approximation of rank. A set of Prolog programs that act as nsefnl tools on algebraic strnctures are created. 11 Acknowledgments I would like to thank, first of all, my co-supervisors . .Jennifer Hyndman and Charles Brown. Jennifer for introclncing me to the world of universal algebra and the countless hours she spent teaching me how to understand rank. Charles for introducing me to the world of Prolog aucl the conntless hours he spent teaching me how to understand coding rank. I also wish to express my gratitude to Professor Bmno Znmbo for breathing new life into my waning entlmsiasm for the research. Thank yon Dr. David Casperson for putting the time aud effort that yon did into reading the thesis. Furthermore, I thank the rest of the l\Iathematics and Computer Science department at UNBC for supporting and guiding me since my first day here. Thank yon my fellow grad students, Erin Beveridge and David Kubert, for listening and helping throughout. Thank yon Roberta Bilons , for putting np with my endless requests with a smile on your face. Thank yon to all the roommates (909 , 1221 , 1282, 1722, and 821) and friends (the university people and the ball people) I have acquired during my Prince George stay, its been real. Thanks Brian Bowman for showing me I can write. Thanks Robert Neil Diaz, Esq. for dragging my lazy bntt ont here and always being there for me. A special thanks to my parents , David and Flora Little, and my brother, Christopher Little, for always supporting my decisions in life without question. Finally, I would like to thank the most wonderful woman in the world , who is also the love of my life, Tracy Bulman. Thanks babe. Ill Contents Abstract 11 Acknowledgments Ill Contents IV List of Tables VI List of Figures Vlll 0 Introduction 1 1 Universal Algebra and Rank 3 1.0 Introdnction . . . . 3 1.1 Universal Algebra 4 1.2 Rank . . . 8 1.3 Summary 16 2 17 Computational Model lV 3 4 2.0 Introdnction . . . . . . . . . . . . . . . . . . . 17 2.1 Problem Analysis - The Experimental Design 18 2.2 Logic Programming and Prolog 21 2.3 The Compntational l\!Iodel 26 2.4 Complexity Aualysis 43 2.5 Snmmary 50 Results and Discussion 51 3.0 Introclnct.iou . . . . . 51 3.1 make_projections /4 52 3.2 rank/6 .. 65 3.3 Snmmary 82 Conclusion 83 4.0 Introdnction 83 4.1 Condnsiou . 83 4.2 Fntnre 'Nork . 85 4.3 Snmmary 87 . . Bibliography 87 A Appendix: Tables 91 B Appendix: Code 119 v List of Tables 2.1 Big-Oh analysis on selected predicates . . . . . . . . . . . . . . . . . . . . 3.1 Rnnuiug times and complexity of make_projections/4 on algebras M 2 and P 2 . Size m = 1. Only 1 snbalgebra for each !.:. . . . . . . . . . . . . . 45 54 3.2 Times to nm make_projections/4 on algebras of size m = 2, for 1 :::; k :::; 3. 57 3.3 Times to nm make_projections/4 on algebras of size m = 2, for 1 :::; k :::; 4. 58 3.4 Times to run make_projections/4 on algebras of size m = 3, for 1 :::; k :::; 2. 60 3.5 Times to run make_projections/4 on algebra, M 12 , of size, m = 3, for 1:::; !.: :::; 3. 3.6 61 Times to run make_projections/4 on algebras of size, m = 4, for 1 < k:::; 2 . . . .. . . . . . . . . . . . . 62 3.7 Average nm times over 1 :::; m :::; 4, and 1 :::; !.: :::; 4 .. 63 3.8 The resnlts of running rank/ 6 on the algebraic operations from algebra, B 15 , to algebra, M 1 . 3.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 . 69 The resnlts of running rank/ 6 on the algebraic operations from algebra, B16, to algebra, M 1 . . . . . . . . . Vl . . . . . . . . . . . . . . . . . . . . 3.10 The resnlts of rmming rank/ 6 on the algebraic operations from algebra, B 9 1 , to algebra , M 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.11 The resnlts of numing rank/ 6 on the algebraic operations fr om algebra, B 9 1 , to algebra, M n (continned ). 72 3.12 The re:-mlts of rmming rank/ 6 on the algebraic operations from algebras, B 11 aml B 12 . to algebra, P 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3. 13 The resnlts of nnming rank/ G on the algebraic operations from algebras, 77 3.14 The resnlts of rmming rank/ G on the algebraic operations from algebras, B 41 aucl B 42 . t.o algebra, P 4. . . . . . . . . . . . . . . . . . . . . . . . . . 78 3. 15 The resnl t.s of nmuiug rank/ G on the algebraic operations from algebras, B 111 . B 11 2 and B 11 :l : to algebra, Pn . . . . . . . . . . . . . . . . . . . . . 80 3.16 The resnlts of nmning rank/ 6 on the algebraic operations from algebras, B 101 , B w2 and B10:l· to algebra, P w . . . . . . . . . . . . . . . . . . . . . Vll 81 List of Figures 1-1 2 (a) An algebra M 1 : (b) a snbalgebra B 1 of (MI) ; (c) (B 1 ) a snbalgebra 1 of (MI)' : and (d) the algebra (M 1 ) 2 I . 10 1-2 The commnt.ing diagram for lifting. 10 1-3 The commnt.ing diagram for rank. . 11 1-4 (a) The algebra M j+k /Y, (b) a snbalgebra B of M 1 , and (c) the algebra B ' a snbalgebra of M~+k . . . . . . . . . . . . . . . 12 1-5 (a) Au algebra Maud (b) C a snbalgebra of M 2 . 14 1-6 (a) The algebra M and (b) snbalgebra B . 16 1-7 Algebra P 1. . . . . . 16 2-1 Algebras M 1 and P 1 . . . 27 28 2-3 Algebras M 9 aud M 12 . 49 3-1 Algebras M 2 and P2 . . . . . 53 56 Vlll 3-3 Algebras P :J. P 4 , P , , and P 5. 56 3-4 Algebras P 7 , P 8 , aud P 9 . 57 3-5 Algebras M 6 . M 7 . and M s. 59 3-6 Algebras M 9 . M 10 . and M n. 59 3-7 Algebras M 12 , P 10 , P n, and P 1 . 60 3-8 Algebras M 1 . and P 12· . . . . . . 62 3-9 (a) The algebra M 1 and (b) the algebra P 1 . 67 f .. 75 . 3-10 The algebra. B 12. a snbalgebra of (P 1 lX Chapter 0 Introduction This thesis presents a system of Prolog based programs for the purpose of approximating the rank of homomorphisms of finite unary algebras. The rank function, introduced by Ross Willard in 1998 [22], is a measure of finite algebras and their operations. Rank is a recursive function of universal algebra and was first introduced as a tool for proving strong dualizability. Logic programming, particularly Prolog, is commonly used in natural language processing, au area of study devoted to the use of computers to understand human (natmal) languages [8]. The general goal of this thesis is to explore a relationship between the fields of Mathematics, Computer Science and Nat mal Language Processing. This thesis presents the hypothesis that wheu universal algebra is viewed as a language, the ideas of natural language processing can be used to create a computer system which approximates rank. The method used to make this link is the design and implementation of Prolog programs 1 which treat universal algebra as a language. The primary purpose of these programs is to create the tools necessary to approximate rank. This link is established through the process of writing code ancl demonstrated with the results obtained from trial nms of the computational model. A further goal of this thesis is to gain a better understanding of the nature of the rank function. The programs contained in this thesis approximate the rank of algebraic operations of finit e unary algebras using a Pro log based system. In Chapter 1, the necessary definitions and theorems from universal algebra are presented as background for the definition of rank. Additionally. Chapter 1 introduces the definition of the rank function , and examines results and examples currently known in this area. Chapter 2 presents the computational model as well as a discussion of the merits of using Prolog for this purpose. Chapter 2 also contains an in-depth look at specific pieces of the code, and their complexity analysis. Chapter 3 includes a discussion of the results obtained from the simulations and a comparison of the actual rnntimes to the complexity analysis of Chapter 2. Finally, Chapter 4 contains the conclusions of the thesis and puts forth a discussion of possible fntnr e work and research in this area. The thesis also contains an appendix of the results presented in tables and an appendix of the code with detailed comments about the various files and fnndors used. 2 Chapter 1 Universal Algebra and Rank 1. 0 Intro d u ction For a greater nnderstanding of the compntational model of Chapter 2, an in-depth look at the rank fnnction is necessary. The rank fnnction is a tool nsed for measurement of finite algebras and algebraic operations in the field of nniversal algebra. Rank was first introdnced as a means of proving strong dnalizability in the area of duality theory. Although this thesis does not deal with duality issues, it is worthwhile to point out the original motivation of the rank function. The dualizability of an algebra is of interest but is beyond the scope of this stndy. This thesis is a study of the mechanisms of the rank function and results obtained with it. As snch, this chapter presents the original definition of rank as well as current results in universal algebra based on the rank function. The first section of Chapter 1 is a brief overview of the definitions and theorems from 3 universal algebra nsecl in ('ctlculating rank. The sec.oncl section defines rank, the K th approximation of rank , and presents some recent results in the area. 1.1 Universal Algebra The concepts from universal algebra that are required indnde those of snbalgebra, congruence, product.. aucl homomorphism. These are developed below, restricted to unary algebras, closely following the notation and terminology of [3]. For A, a nonempty set. and n , a nonnegative integer. we define A 0 = {0} , and, for n > 0, An is the set of n-tnples of elements from A. The ca1·dinality of a set, A, written IAI, is the number of elemeuts in the set. An n-ar-y r-elation on a set, A, is a subset of An. If n = 2, it is called a hirw.r-y r-elation on A. A binary relation e on A is an equivalence r-elation on A if. for any o. h. and c from A , it satisfies: El: (a . a) E (} (reflexivity); E2: (a. h) E (}implies (b, a) E e E3: (a. h) E fJ and (h, c) E 8 imply (a , c) E 8 (transitivity) . (symmetry); The functiou . f : A---... B. is said to b e one-to-one iff (a 1) = f (a2) implies a 1 = a2. Furthermore, the fnuction. f : A ---... B , is onto if for every h E B there is an a E A with f (a) = b. An n- ar·y operntion (or function) on A is any fnnction , f , from An to A; n is the ar-ity of f. A finitar-y operatiou is an n-ary operation, for some finite n. The image of (a 1 , ... , an ) nuder an n-ary operation, f, is denoted by f (a 1 , ... , an)· An operation is 4 unary if its arity is 1. A language (or type ) of algebras is a set J of function symbols snch that a nonnegative integer n is assigned to ea('h member f of J. This integer is called the arity of f , and f is said to h e an n-o:ry function symbol. The snbset of nnary fnnction symbols in J is denoted J 1 . An alg ebTa A of type J 1 (a nnary algebra) is an ordered pair, A = (A, F), where A is a nonempty set and F is a finite family of nnary operations on A indexed by t he langnage, J 1 , Sll('h that ('Oncsponcling to each m1ary fmwtion symbol, f , in J 1 there is a nnary operation. fA. 011 A. The set , A, is called the unive rse (or undeTlying set) of A , and the fA 's are called the fundo:m ental operations of A . In practice it is common to write jnst f for fA and often to write (A, fi, ... , fk ) for (A. F ) . A mono-unaTy algebra, M = ("!II, f) , is an algebra with one nnary fnnction , a bi-unary algebra, P = (P. fi . h ), is an algebra with two nnary fnnctions, and so on. Throughout the rest of the thesis au algebra refers to a nnary algebra. Let A and B be two algebras. Then B is a subalgelrm of A if B ~ A and every ~ fundamental operation of B is the restriction of the corresponding operation of A , i.e. , for each fnnction symbol f , fB is f A restricted to B ; we write simply B :::; A. A subuniverse of A is a snbset B of A whi('h is dosed nnder the fnndamental operations of A , i.e. , iff is a fnndamental operation of A and a E B we reqnire f (a) E B . Thns if B is a snbalgebra of A , then B is a snbnniverse of A . Note that the empty set may be a snbnniverse, but it is not the nnderlying set of any snbalgebra. 5 Let A b e an algebra and X a subset of A , then Sg (X)= n {B: X s;;; Band B is a snlmniverse of A}. The notation, Sg (X) , is read as the subuniverse gen erated by X . Theorem 1 L et A= (A, F ) be an algebra and X a subsr:t of A. Th en , Sg (X) is generated recursively, as follows . Sg (X) = UX;EJ, where Xo = X and Xn+l = Xn U {f(a): f E Fo E Xn}Suppose A and B are two algebras . A function , h : A ---+ B , is called a homomorphism from A to B if for all fundam ental operations, f , in J 1 and each a from A. A homomorphism, h : A ---+ B , is an embedding of A into B if h is one-to-one and it is an isomorphism from A to B if it is one-to-one and onto. Let A b e a n a lgebra a nd B :::; A n. The homomorphi sm s, h : B ---> A , for a ll positive integers, n, are called the algebraic opemtions of A. Theorem 2 Suppose h : A ---+ B and g : B---+ C are hmnmnorphisms. Th en the composition g o h is a homomorphism from A to C. Theorem 3 If o : A ---+ B is an embedding, then a (A) is a subuniverse of B . 6 If o: A ---+ B is au embedding , o: (A) denotes the snbalgebra of B with nniverse a (A). Let A be au algebra and let e h e an equivalence relation. Then e is a congruence on A if for each fnuctiou symbol f E J 1 and elements a , h E A, if (a, b) E e then Let h : A ---+ B he a homomorphism. Then the kernel of h , written ker (h) , is defined by ker (h)= { (a, b) E A 2 : h (a) = h (h)}. Theorem 4 Let h : A ---+ B he a homomorphism. Th en ker (h) is a congruence on A. Let A b e au algebra ancllet e he a congruence on A . The natural map "' : A---+ A / 8 is defined by /{.(a)= aj e. Theorem 5 Th e natuml map from an algebra to a quotient of th e algebra is an onto homomorphism. Let A 1 , . . . . A, hen algebras. Define the product, A 1 x · · · x An , to be the algebra whose nniverse is the set , A 1 x · · · x An , and snch that for f E J 1 , a 1 E A 1 , . .. , an E An , ! A jX···X A , (( al , .. . , an ) ) -- \I JA l ( al ) . ... , JA n. ( an ) ) . 7 The mapr)ing 1fi : A 1 X . . . X An - A;' i E { 1' ... ' n} ' defined by is called the JnOj P.ction rnop on the i'-h coordinate of A 1 x · · · x An. Theorem 6 Fri1' i = 1 . . . .. n , th e mapping, 1f; A 1 x · · · x An - Ai, is a surjective homomorphisu1. fmm A = A 1 x · · · x A, to A;. If A; = A for all i E { 1. ... , n } , then the product is written A n and is called it a power of A. 1.2 Rank This section provides us with the definition of rank. It also gives some of the current results whi_ch relate to rank. The definition of rank is taken directly from [10], which :.:?'.. ':" is based on the original definition given by Ross \iVillard in [22] . In \iVillard 's paper, he developed the concept of rank and then used it to prove that all finite algebras with a finite rank that are dualizable are strongly dualizable [22 , Theorem 4.1]. This, in turn, was motivated by the attempt to prove that the ring, 2 4 , is strongly dualizable in [6], in which it is proved implicitly that the rank of any finit e commu tative ring with identity whose Jacobson radical J satisfies .P = 0 is less than or equal to one. To reiterate a 8 point made earlier, dnality theory is not covered by this thesis, bnt some terms and ideas are mentioned to provide the motivation for rank . Let M b e a fixed finit e algebra, n a positive integer , and B a snbalgebra of M n. Also, let h be a member of the set of all homomorphisms from B to M (written Hom (B , M )). For algebra, B ' , a snbalgebra of M "+k, for some finit e J..: , the notation, B =>a B' , denotes rr : B-----+ B ' is au embedding via repetition of some coordinates . The homomorphism, h' = rr- 1 o h , is the natmal extension of h to B' . Throughout the thesis, in the diagrams nsed to represent. algebras, au arrow from element, .T, to element , y, denotes the fact that f (x) = y. For notational convenience, (x 1, x2, ... , .T,) E Nfn is denoted by x 1x 2 · · · Xn· Example 1 Referring to Figme 1-1 , let M 1 be the algebra represented by Figure 1-1 (a), which has universe Af = {O . o., b,c}. Figme 1-1 (b) shows an example of a subalgebra B 1 of (M 1 f Letting k = 1. algebra, (B I)' , is a subalgebra of (M 1 ) 3 , where B 1 embeds into (BI)' by rr (ha) = hha , a repetition of the first coordinate. Algebra, (BI)' , appears in Figure 1-1 (c). Let B' :S C :S D :S M n+k and let Y ~ Hom (D , M ). The algebra, D / Y, denotes the algebra D jn {ker (g) 19 E Y} and C / Y the algebra C jn {ker (glc) 19 E Y}. The set, Y , separates B' if n {ker (gl B') lq E Y} = OB'. The notation , OB', represents the congruence, OB' = {(.x, .T) : ~ E B '}. The homomorphism , h' , lifts to C / Y if Y separates B' and t here exists a map I·" !:iuch t hat the diagram in Figure 1-2 commutes. A diagram is said to commute if the composition of functions over any path of arrows from t he same starting algebra to the same final algebra results in the same homomorphism. 9 (a) M1 (b) B 1 (c) B 1 ' ha bba ~ ~ (' h • Va I • • •a (d)M/ • r:r: Oc ac he cO r a r h 0/1 hO ha biJ ah • • • • • • • • • • • • ! \!/• Oa \ •!/aO • aa ~~ LtOO 2 Figure 1-1: (a ) Au algebra M 1 ; (b) a snbalgebra B 1 of (M 1 ) ; (c) (B I)' a snbalgebra of (M 1 ) 3 ; and (d) t.he algebra (MI) 2 . B' c < h' fl. M------ C/ Y J-L Figmc 1-2: The commuting diagram for lifting. Definition 7 (Rank) Given a homomorphism, h : B --t M , then rank (h) ::S: 0 if and only if h is a pmjectwn . Th e rank (h ) ::S: o: if and only if there exists a finit e N such that for all nonnegative integers. 1.:, fo r all subalgebras, D , of M n+k and for all comm'u ting diagrams , shown in Figure 1- S, where th e homomorphisrn h' lift s via h+ to D , th ere exists Y ~ (D , M ) such that IYI ::S: N , h' lifts to C / Y , u.nd ra:nk (gl c ) < o: for all g E Y. 10 > B' B c < IT < / D / / h' h / h+ / / / M / Fignre 1-3: The commuting diagram for rank. The equality. Tanl.: (h) = n:, holds if and only if Tan/.: (h) ~ a and not Tank (h) < a. If there is no such finit e n:. then write Tank (h) = oo . The rank of M , Tank (M) , is the supremum of the ranks of all the algebraic operations of M . The following example gives an illustration of the steps involved in finding the rank of a homomorphism. Example 2 Let. M 1 he the algebra given in Example 1 on page 9. Let B be the two element subalgebra of M 1 , { 0, b} of Fignre 1-4(b) and let n = 1. Also , let N ~ 1 and h : B -+ M 1 be the homomorphism given by h (h) = a and h (0) = 0. Let x = (.r , x, ... , x) E (M 1 )l+k, where x E M 1 . For any fixed nonnegative integer , k, the algebra, B' , in Figure 1-4(c) , is a subalgebra of (M 1 )I+k and B embeds into B' by repetition of coordinates. The homomorphism, h' : B' -+ M 1 , is given by h' (E) = a and (5) = 0. For all B =>a B' ~ C ~ D ~ M ~+ h' lifts to D via the homomorphism, h* : D -+ M defined by h* (E) = a, h* (5) = 0, and sending everything else to 0. h' 1, The set, Y = {1rl} s;;; H orn (D , M ), is a set of one homomorphism from D to M 1 that separates B' . The algebra, M ~+k /Y, is the fact or algebra { [i)]y, [a]y, [E]y, [c]y} of Figure 1-4(a). There exists a homomorphism, J-L : C / Y 11 -+ M 1 , defined by J-L ([EJ y) = a, f-L ([5Jy) = 0 and p sends everything else to 0. The homomorphism , h' , lifts to C / Y by f-L· Since IYI = 1 :::; N aud rani.: (ni) :::; 0, then rank (h) :::; 1. (a) M 1l+k (h) B ~ • [i!ly •I [r1h· b • \/ . Lt [O]y ~ Fignre 1-4: (a) The algebra M~ +k a snbalgebra of M }+k. (c) B' b • \ L!O (h) a snhalgehra B of M 1 , and (c) the algebra B' The definiti on of rauk incndes the nniversal qnantification 'for all nonnegative integers k:. ' The following ddinitiou changes this nniversal qnantification to a bonnded qnantificatiou. Definition 8 The 1-,:th. appro.rimation of rank is the same as rank (Definition 7), except that 'joT all nonnegative integers, /,:,'is Teplaced by joT all/,: :::; K for a fixed finite K. ' The following resnlts are t aken directly from [10], in which it is proven that mononnary algebras have rank at most two and thns are strongly dnalizable. It is necessary to start with some preliminary definitions , lemmas aucl theorems before getting to the main point of the paper . A connected component of a m ono-nnary algebra is a snbalgebra B that is maximal with respect to the property that for all a, bE B , f m (a) = f 5 (b) for some m , s 2:: 0. Let M = (!11. f) b e a finite mono-nnary algebra. Let C :::; M 11 , where n is a finite positive integer. Let A be a connected component of C. The essential components 12 of A are the mininmm set of connected components of M that contain 1ri (A) for all proj ections 7r; . The cor-e of a connected mono-unary algebra is a nonempty subalgebra on which f is a one-to-one fun<'tion. In a finit e, connected mono-nnary algebra the core will b e of the form {a , f (a) . F (a )' ... ' r-l (a)} , where fk (a) =(/,and k an integer. An arbitrary finite mono-m1ary algebra may have several cores. The ciTC1J:rnfe-i·ence of the connected component A , eir-e (A) , is the least k such that for some a. E A. r (a) = a. That is, the circumference of a finite, connected mono-unary algebra is the size of the core. For .r E C snd1 that .T is not in a core bnt f (x) is in a core, the set {y E Blfm(y) = x for some m 2:: 0} is a bmnch. ~ E C , :r: is a bmnch elem ent if .r is an element of a branch. For x a branch elem ent , the COh eig h.t of T is the greatest k SUCh that there exists a y with r (y) = X. For x a core element coh eig ht (.r) = oo. An illustration of the above definitions is made in the following example. Example 3 Let M be the mono-unary algebra {a, h, 0, 1} shown in Figure 1-5(a). M has two connected components , call them M 0 = {a, 0, 1} and M 13 = {b} . C = {aa , ab , Ob , OO , 1h.ll} , given in Figure 1-5(b), is a suhalgebra of M 2 . C also has two connected components, call them Aa = {aa , 00 , 11} and A 13 = { ab , Ob , 1b}. For A 0 , the 13 essential component is M n, it has the core {00 , 11} , eire (A I) = 2 and it contains one branch with one brauch element aa with coheight (aa) = 0. The connected component, A p, has essential components M o- and M p, core {Ob , 1h} . circumference 2 and branch element ab wi th rohe'i ght (ah) = 0. (b) (a) M c b (j Figm e 1-G: (ct) An algebra M and (b) C a subalgebra of M 2 . Lemma 9 L et A he a cor1:nected component of C and M a an essential component of A . Th en th e circumJP-n:n ce of A is a (positive) integer· multiple of the circumf erence of M a. For A a connected component in C and M a an essential component of A , to wrap A around M a means to define a homomorphism, q, from A to the core of M a recursively as follows . Pick a E A and din the core, L , of M a. Let q (a) = d and q (Jm (a)) = fm (d). If q is defined ou f (.1:) hn t uot defined on x then let q (.7:) E f- 1 (q (J (.x))) n L , which has exactly one element in it . i.e. the one l E L that is sent by f to q (J (x)). Lemma 10 Let B 1 . . . .• B 1 be the disjo int connected components of an algebra B . L et hi : B i ..-.-.r M be lwrnmrw r7J hisms. Th en h = Uh; is a lwrrwrnorphisrn frorn B to M . For a branch element b = (b 1 , .. . , bn) E B define homomorphism, gb : B ..-.-.r M , as follows. Let A 1 be t he connected component of B with b E A 1 . Pick u in an essential 14 component, M a. of A 1 snd1 that coheightM ('u) is finite and maximal over all elements in essential components of A 1 . Lett= coheightB (h). Define .9b (b) = u. For any x in B and any s with 1 :::; s :::; t where rs (.r) = b define .9b (.r) = p-s (v). Wrap the remaining elements of A 1 aronnd the core of M a sp ecifying .9b (f (b)) = f ('u). By Lemma 10, we may extend g1, by wrapping each connected component A 2 , distinct from A 1 , around an essential comp011ent of A 2 . Theorem 11 For h n lrm:ru:h elem.ent of B , Tanl• (g,) :::; 1. Theorem 12 FoT B :::; M " and h: B ---+ M a homomorphism, rank (h) :::; 2 . Example 4 Consider the algebra M h with four elements {0 , a , b, c } , of Figure 1-6(a). Here we illustrate that M 1 has rank 2. Let B = {0, a}, the universe of the algebra, B , shown in Figure 1-G (b). Consider the homomorphism h: B ---+ M 1 given by h (a) =band h (0) = 0. Fix N ~ 1 and let k ~ N. Let D = M~+ {c} and let B = >a B' :::; C :::; D . Then h', the natural extension of h to B' , lifts to D . Neither a has a pre-image in D nor does h' (a) have a pre-image in M 1 • Let Y be a collection of fewer than N projections, then [a]y has a pre-image in D / Y. Thus h' does not lift to D / Y . In order for h' to lift to D / Y , Y must have either 1.: + 1 projections or a non-projection. Since k can be arbitrarily large and IYI :::; N which is fixed , Y must contain more than just projections and thus by Theorem 11 rank (h) ~ 2. By Theorem 12. rank (h)= 2. Finally, in [11] Hyndman and Willard show an example of a finite algebra, P 1 , which is dnalizable but not fully clualizable. This algebra is shown in Figure 1-7. This result 15 h • I (b) B c • •a \I cjO I a • cjO Fig;nre 1-6: (a) The algebra M and (b) snbalgebra B . implies that the rank of P 1 is infinite by [22, Theorem 4. 1]. Figure 1-7: Algebra P 1 . 1.3 Summary The rank of an algebra and its algebraic. operations is based on the terms of universal algebra ~ in this chapter. The rank of an algebra is a tool used for proving strong dnalizability. It has been shown that finite algebras with a finite rank that are dnalizable are strongly dnalizable, mouo-nnary algebras have a finite rank, that the ring Z 4 has rank one, and that the rank of P 1 is infinite. 16 Chapt er 2 Computational Model 2. 0 Introductio n This chapter provides a brief overview of the goals of creating t he computational model and a breakdown of the necessary steps taken to achieve these goals. The broader goal of this research is to unify the application of the fields of Mathematics, Computer Science and Formal Languages in a relevant and practical way. The specific goal is to create a computer based system for the purpose of approximating the rank of a finit e unary algebra or algebraic. operations of a finite m1ary algebra using the methods of language models . To attain the specific goal of approximating rank computationally it is necessary to break it down into several sub-goals. These sub-goals include the design of the model, selecting a language to work with. writing and implementing code, and analyzing the code. The goal of using Mathematics, Computer Science, and Formal Languages in unison is attained by 17 implementing the code, rmming trials , and gathering results. When the results provide support to known theoretical resnlts and are consistent with what is known then we are confident that the applicatiou of these fields is correctly united. The first section of Chapter 2 looks at the design of the computational model. The second section poiuts ont the advautages of using logic programming, specifically Prolog, for this thesis. The third section in this chapter presents the computational model. This section is where the ideas of the previous two sections are brought together. In the final section a detailed complexity analysis of the code is given. The complexity analysis consists of timing analysis clone on the algorithms used. in Big-Oh notation. 2.1 Problem Analysis - The Experimental Design One of the goals of this research is to create a compntational model using the ideas of language processing to approximate rank. In order to write programs for any purpose it is necessary for a programmer to decide on a programming language. Furthermore, before programmers select a language they need to outline the problem and define what the programming langnage ueeds to provide. This section is the starting block for the programming process, in which the problem at. hand is dissected and studied to provide motivation for the choice of programming langnage. The purpose of the rank fnncti on is to measm e algebras and homomorphisms. The first thing needed is to define data structures to represent algebras and homomorphisms on algebras. An algebra is defined in Chapter 1 as a set of elements, or universe, with 18 a list of unary functions defined on the set. A homomorphism is a mapping, defined on the elements of an algebra, from the algebra to another , which respects the operations. There is no restriction on the elements that can be used in an algebra or a homomorphism. For both, the best choice of data strnctnre allows for manipulation of general types of elements. Representing the elements symbolically, allows for more freedom in the choice of algebras and homomorphisms than when confined to numerical representation. Fnrthermore, it would be beneficial to have a readable representation of an algebra and homomorphism. Although the data stmctnres corresponding to algebra and homomorphism are similar in natmc. it is uecessary to be able to easily distinguish between the two. The rank of an algebraic operation is recnrsively defined using ranks of simpler algebraic operations. The rank of an algebra is defined in terms of the ranks of the algebraic operations of that algebra. This implies that it is necessary to have a store, or database, of homomorphisms of knowu rank. To start, the database would consist of projections which by definition are rank less than or equal to zero. It is highly probable that this database will b e very large aud will constantly grow. Optimistically, the database should have the capability of storing large amounts of information while at the same time be easily and quickly accessible to the calling program. In addition, it would be advantageous to be able to add new homomorphisms to the database as their rank is discovered. The definition of approximate rank is recnrsive with base case determined by projections. Moreover, the procednres used to generate subalgebras and homomorphisms from 19 a given set are recursive. As a result, it is most effective to write recursive computer programs to compnte approximate rank. Generating all the possible snbalgebras of a given algebra is necessary in creating the database of projections and in approximating rank. Furthermore, in the definition of rank it may he necessary to exhanst all the possible sets of homomorphisms with known rank. Therefore. the model shonld be capable of generating and exhansting all the possible solntions to a particnlar problem. In some cases, it is necessary to use all the solntions possible in the search, \:vhile at other times one need only search the possible ontcomes nntil an appropriate ontcome is reached. The difference here depends on the qnantification, it reflects the difference between the statements for all and there exists. These restrictions imply a need to have strict control of the overall flow of the program at any given time. To smnmarize, the compntational model mnst be capable of exhausting all possibilities for a single goal while at the same time knowing when to cut that search off. So far the discnssion has centered aronnd the general issnes and encompassing feel of programming rank. One more issne needs to be addressed. To properly code the approximation of rank. many tools from nniversal algebra are nsed and need to be written as sub-rontines to be called by the rank routine. These indnde, embedding an algebra, B, into algebra, B'. by the repetition of some k: coordinates; separating an algebra, B', by a set of homomorphisms , Y; factoring the algebra, C , by the set, Y; extending partial homomorphisms in conjnnction with determining lift from a homomorphism, h', to an 20 algebra, D , or factor algebra. C / Y; as well as some more trivial tools. Thus, in order to complete a compntational model for rank approximation , the coding of some additional tools is necessary. Finally, \vith the problem defined and the goals decided upon the next step is to discuss the choice of programming language. Upon inspection of the goals, the tools and structures needed for the type of system to be created , the logic programming language, Prolog, is the langnage of choice. The following section presents the reasons for this decision. 2.2 Logic Programming and Prolog Logic programming is programming with the use of languages based on the foundations of predicate logic , as opposed to the more traditional , structured programming langu ages (e.g. Cor Pascal ), or obj ect oriented programming languages( e.g. C++ or Java). Prolog [12] is the most popnlar logic programming language. It. is based on a subset of possible formulae , called Horn clausr:s, from first-order predicate caknlus (FOPL). In this section of Chapter 2, the advantages of logic programming, specifically Prolog, as a programming language are discnssecl. The section is divided into six subsections, each representing a particular advantage of Prolog. \"lithin each subsection the general advantage is given followed by an explanation of how this relates with the particular goal of the research. One of the original motivations for doing this research is the idea that the language of universal algebra may b e viewed in terms of a formal language. That is, in a general 21 sense, universal Rlgebra can he seen to have a syntax (rnles) , sem ant irs (meaning), and a lexir on (facts). For example. there is a rnle of English langnage t hat says, "a stat em ent is a sentenre if it is comprised of R nonn phrase followed by a verb phrase." Similarly, it ran b e said that nuiversal algebra has t he rnle, "an algebra , B = ( B , JB ), is said t o be a subalgebra of an algebra , M = (A1, JM), if B , t he universe of B , is a snbset of M , and JB is d osed nuder the operation of M , JM ." Also. nniversal algebra has sem antirs, the algebras, M aucl B , conld b e examples of various different typ es of algebras. In t his rase, it is known that. M and B are mono-nnary algebras , based on t he context of the t hesis aucl t he way t he algebras are presented within the sentenre. Furthermore, in English , a seut.euce is made np of words form a lexicon. where a lexiron represents the database of all knovvn Euglish words. Wit h regards t o t he st atement ab ove, there m ay b e a lexicon containing objects whirh are viable elements of an algebra and/ or a lexicon of known algebras. Sp ecifi c to the researrh of this thesis, universal algebra ran b e seen to have a lexicon of homomorphisms wit h known rank. Prolog is a logir based programing langnage that is nsed in some areas of Artificial Intelligenre, in particular ""F.r..;.· Natural Langu age P rocessing. Natural Language Processing is loosely defined as t he study of natural hmnan laugnages nsing r ompnters. Taking in to r onsideration the romparison of nniversal algebra to formal langnages mentioned , t he nse of Prolog for the purposes of t his t hesis seems a natural fi t . Vlith t he idea t hat P rolog wonld be t he right rhoire for this thesis , a deeper investigation into other advantages of its use follows. Prolog allows for the manipnlation of symbolir dat a as oppose to nnmerir data. This 22 is done through the nse of data types snch as atoms , predicates, lists and list structures coupled with nnbonnd variables and nnification. This nse of symbolic processing in Prolog is less restrictive than nnmeric compntation langnages. Great freedom is allowed in the choice of operations that can be performed and the elements that can be nsed in these operations. Vvhat the symbolic processing capabilities of Prolog gives a programmer is qnalitative representation of knowledge. Algebra is abstract.: the elements and operations done in nniversal algebra reside on the symbolic level and thns are snited to symbolic representation. So , in relation to the problem analysis of the first section, Prolog is an advantageons programming language for its capability to represent the structures of the algebra and homomorphism symbolically. Prolog programs are basically a database of rules and facts given within a specific domain. The idea is to query the program and based on these rules and fads, Prolog answers the query hy possibly generating new knowledge in the domain. The whole process can be looked at as database manipulation on a relatively small scale. One of the advantages of this fact is that Prolog allows yon to describe general ideas while at the same time define specific situations. Furthermore, this allows code to be compact and to the point, since rules are generally small and geared toward specific goals. Also, because Prolog rules tend to be small and variables are locally quantified, any changes that need to be made are local. As mentioned above, caknlating rank is also based on a set of rules and facts. The rules being the steps involved in finding the rank of a homomorphism. The facts are a store (database) of homomorphisms with known rank. Initially, the database 23 contains only projections. Homomorphisms whose ranks are discovered are added to the database. One of the major program control constructs of Prolog is recursion. What this means is that the predicates written in Prolog are normally defined recursively. With recursion one can represent the usual constructs, for loops and irthan-else statements, as well as make it easier traversing through such data types as the list. For example, in traversing a list with recmsion. the size of the list need not be known, which is not necessarily true of the above constructs. l\Ioreover , recursion in Prolog is more readable, it is easy to follow where a predicate is going and what its goal is. Since recursion is a more concise construct, it makes it easier to analyze for complexity. With Prolog the rank function can be written recmsively taking advantage of the rank definition's bnilt in recursion. Another major drawing point of Prolog is its ability to move backwards, or backtrack, through code. In other words, Prolog has the ability to search the entire proof tree for all possible outcomes of a query by redoing earlier computations and trying other solutions. Among other things. it allows the programmer to get more ont of one predicate with minimal extra work clone. Iu calcnlating rank it. is necessary to find all the snbalgebras of a given algebra at varions points. With backtracking available, one need only write code that will generate an arbitrary snbalgebra. The backtracking feature makes possible finding all the arbitrary snhalgebras using this code. One control construct used by Prolog, recursion, has already been mentioned. Another control constrnct in Prolog is the pattern-directed search. The control this exerts 24 comes in the form of the bnilt in nnification and depth-first search algorithm. By corredly ordering predicates one has control over where the search goes and where variable unification takes place. Fnrthermore, Prolog offers some procedural features such as assert , fail , and the cnt. denoted by an exclamation mark, ( ' ). The dause assert allows the programmer to add new predicates to the database during runtime. The fail causes the code to backtrack at any point in the code, and the cut controls the path of the search tree ·while backtracking. Control is a very important aspect when calculating rank, in a few different \vays , which is why the flexibility of control offered by Prolog is attractive. First of all , when choosing homomorphisms for a set, Y, it is necessary to start with the homomorphisms of lowest rank and work up . Second, one needs to b e able to add new homomorphisms to the database at rnntime b efore trying the next homomorphism. The search tree for the rank function is deeply nested and can become rather large when the number of snbalgebras grows quickly. There are two situations to control when travelling throngh the search tree of rank. One, if at any time something fails to b e trne about a subalgebra, the whole program shonld fail. Two , if a particular homomorphism extension. h' , or set of homomorphisms , Y , fail , then move on to the next one. For all these instances Prolog offers control devices to cope with them. For all these reasons the best choice of programming langu age for this research is Prolog. Now , to introclnce the code and explain the inner workings of its particulars. 25 2.3 The Computational Model Section 4 of Chapter 2 describes the final incarnation of code that constitutes the computational model. The model approximates the rank of homomorphisms on algebras. Not all aspects of the model are presented here, for a complete look at the code refer to Appendix B. The first. part of this section gives an introduction of the datastructnres which represent algebras ctnd homomorphisms . In the second part , a discussion of the database of homomorphisms \vith known rank is given. The fin al three parts of this section present t.he main body of code, rank/6. These three sections are divided into three major themes of rank/6 , the use of recursion , the use of bagof /3 and set of /3 for all possible solutions. and t.he use of the cut for control of ftow. As discussed in the previous sections of this chapter. the basic building blocks of the rank definition are the algebra and the homomorphism. It. was decided that the best way to represent these stmct.nres is symbolically. In Prolog this means the use of functors, lists or a combination of the two. For this model an algebra is represented by a functor with two arguments , cctlled algebra/2. The first argument. of algebra/2 , which represents the universe of the algebra. is a list. containing the elements of the universe, where each element is also given as a list. The second argument is a list of lists representing the unary functions of the algebra. Each sublist in the second argument represents one unary function on the algebra. A function list is made up of one or more instances of the functor , f /2 , one for each element. in the universe. The functor. f /2 , has two arguments, both elements of the underlying universe of the algebra. The first argument is the element 26 M1 ~ I pl c 'i-' b • !+ rt a I •a \fa do Figure 2-1: Algebras M 1 and P 1 . being mapped and the secollCl is the image of the first after applying the function. For example, algebras M 1 and P 1 , given in Figure 2-1, are represented as follows: For M 1 , algebra([[o], [a], [b], [c]], [[f ([o], [o]) , f ([a], [o]). f ([b], [o]), f ([c], [a])]]) , and for P 1, algebra([[o], [a], [b]], [[f ([o], [o]) , f ([a], [0]) , f ([b], [a])], [f ([o], [a]) , f ([a], [b]) , f([b], [b])]]). To show the reasoning for representing elements of the algebra as lists, let us look at another example. Given algebra M 3 with universe M?. = {0 , a} , the algebra (M 3 ) 2 has universe (M3 ) 2 = {(0 , 0) , (0 , a) , (a , 0) , (a , a)}. Both algebras are shown in Figure 2-2, 2 and the Prolog representation of (M 3 ) in this model is algebra([[o, o], [o, a], [a, o], [a, a]], [[f ([o, o], [o, o]) , f ([o, a], [o, o]) , f ([a, o], [o, o]) , f ([a, a], [o , o])]]). 27 M3 M3 2 a Oa. rw aO (jO (jOO \I/ I For the compntational model of this thesis, a homomorphism is represented by fnnctor, homomorphism/5 . Generally, the datastrnctnre for a homomorphism from an algebra, AlgB , to an algebra. AlgM, looks like homomorphism(Rank,K , AlgB , AlgM, Homo ), where AlgB is a snbalgebra of algebra, (AlgM)n , for some finite, nonnegative n , and arguments Rank . K, and Homo are as follows . The variable, Rank, is the Kth approximation of the rank of the homomorphism, Homo , where K represents a fixed finite integer. Variable Homo is a list containing two other lists. The first list in HOMO represents the domain of the homomorphism and the second is a list of two-argnment fnnctors , h/2 , which represent the image, after applying the homomorphism, of each element in the domain. As an example, snppose we have a homomorphism from algebra, (M 3 ) 2 , to algebra, M 3 , which 2 maps every element in (Jlf1 ) to the element, 0 , in the nniverse, M.3 . Then, the variable 28 Homo would bind with the list. [[[o, o], [o. a]. [a. o], [a. a]], [h([o , o], [o]) , h([o, a], [o]). h([a, o], [o]), h([a, a], [o])]]. The inclusion of the variable K as an argument of homomorphism/5 is necessary for the computational model. The J{ th approximation of the rank of a homomorphism is dependent on K, so the value of K, for any given homomorphism, is needed to make correct conclusions about reported ranks . Recall , the approximation of the rank of au algebraic operation is based on the rank of other algebraic operations. Tlms , it is necessary to create and maintain a database of homomorphisms with known rank. The database consists of assertions which are provided by headless predicates, each of the form homomorphism(Rank,K , AlgB , AlgM, Homo) . Furthermore, the definition of rank , given in Chapter 1, states that rank (h) :S 0 if and only if h is a proj ection. This gives the initial set of homomorphisms for the database onto which more will be added. The database consists of two directories , MUDatabase and BUDatabase, the latter being the database of homomorphisms on bi-unary algebras, and the former t he database of homomorphisms on mono-unary algebras. Each directory consists of multiple files containing the homomorphisms on particular algebras. The files are named for the algebra with the Prolog extension pl , since it is necessary to consult 29 the appropriate file. The predicate, make_projections/4 , is used to create, for a fixed algebra, the init ial database of proj ections, all of which have rank less than or equal to zero. The proj ections being used are those from all the subalgebras of finite powers of an algebra, up to a fixed size, to the algebra. The code for make_projections/4 is as follows. % make_projections(+ALG_M,+I,+K,+FILE) % Create a database of projections from subalgebras of finite % powers of algebra, ALGJM, to ALG_M, for 1 < = I < = K. Store the % database as a file with filename, FILE . make_projections(algebra(M,FM),I,K,File) open(File,write,Stream), list_to_ord_set(M,OM), ord_functions(FM,OFM), for_each_i(algebra(OM,OFM),K,I,Stream), close(Stream). % for_each_i( +ALG_M,+K,+I,+STREAM) % For each integer, I, from 1 to some integer, K, construct the Ith % power of algebra, ALG_M, and collect all the subalgebras % of the resulting algebra. for_each_i(Algebra_M,K,I,Stream) :I= < K, ! , make_M_to_the_n(Algebra_M,I,AlgebraJMi), bagof(Algebra_B,subalgebra(Algebra_B,AlgebraJMi),Subalgebras), for_each_sub(Subalgebras,AlgebraJM,I,Stream), I1 is I+1, for_each_i(Algebra_M,K,I1,Stream) . for_each_i(Algebra_M,K,I,Stream) . % for_each_sub(+SUBS,+ALG_M,+I,+STREAM) % Recursively traverse the list of algebras, SUBS. for_each_sub( [] ,Algebra_M,I,Stream). 30 for_each_sub ( [Alg_B IAlgs_B] , Algebra_M, I, Stream) for_each_j(Algebra_M,I,Alg_B,l,Stream), for_each_sub(Algs_B,Algebra_M,I,Stream) . % for_each_j(+ALG_M,+I,+ALG_MI,+J,+STREAM) % For each integer, J, from 1 to integer, I, construct the list % of projections from an algebra, ALG_MI, to algebra, ALG_M, % write them onto the stream, STREAM, as clauses of the % predicate, homomorphism/5. for_each_j(Algebra_M,I,Algebra_Mi,J,Stream) ·J= < I, ! ' projections(Algebra_Mi,J,Homomorphism), write(Stream,homomorphism(O,'K' ,Algebra_Mi,Algebra_M,Homomorphism)), format(Stream,' '-w'', ['. ']), format(Stream,''-n ' ', []), format(Stream,''-n '' , []), Jl is J+l, for_each_j(Algebra_M,I,Algebra_Mi,Jl,Stream). for_each_j(Algebra_M,I,Algebra_Mi,J,Stream). % projections(+ALG,+J,-PROJ) % Argument, PROJ, binds with the homomorphism list created by % taking the Jth projection of each element a in an algebra, ALG. projections(algebra([] ,Functionlist),J, [[], []]) . projections(algebra([X!Xs] ,Functionlist),J, [[X !Restl], [h(X,Y) !Rest]]) proj(J,X,Y), projections(algebra(Xs,Functionlist),J, [Restl,Rest]). There are 4 arguments for this predicate, ALG_M, I , K, and FILE, all of which are bound variables, meaning the 4 variables of this predicate are expected to b e input by the user. The variable, ALG_M, represents the underlying algebra . Variable FILE is the particular fil e which the part of the database for ALG_M is stored in. For example, the database for algebra M 1 of Fignre 2-1 , is stored in file 1 MUDatabase/algebraM1.pl' . The database 31 contains information abont homomorphisms on snbalgebras np to a finite power of an algebra. The variable. K. represents the finite power, which may be different from algebra to algebra. In the case of proj ections, t he variable K remains an nnbonnd variable in the database, which hinds to m1y value of K used. Projections are of rank 0 no matter what value of K, by the definition of rank. Finally, the variable, I , is used as a counter np to K, which nsually hegins as 1. As an example of a database entry, consider again the algebra M 1 of Figure 2-1 , and algebra B 11 a subalgebra of M f. Let algebra B 11 be defined as follows , algebra ( [ [0, 0] , [a, b]] , [ [f ( [0, 0] , [0, 0]) , f ([a, b] , [0, 0])]]) , where t he first proj ection, 1r 1 . from B 11 to M 1 is defined as [ [ [ 0 , 0] , [a , b] ] , [h ( [ 0 , 0] , [ 0]) , h ( [a , b] , [a]) ] ] . The entry in the database file 'MUDatabase/algebraMl . pl' looks like this: homomorphism(l,K, algebra ( [[0,0], [a,b]], [[f([O,O], [0,0]) ,f([a,b], [0,0])]]), algebra( [ [0] , [a], [b] , [c]] , [ [f ( [0] , [OJ), f ([a] , [OJ) , f ( [b] , [0]) , f ( [c] , [a])]]) , 32 [ [ [ 0 , 0] , [a , b] ] , [h ( [ 0 , 0] , [ 0]) , h ( [a , b] , [a] ) ] ]) . So far , in this section. the basic datastrnctures used in the computational model and the code used for the creation of the database have been covered. Consider this the setup to the main programming that needs to b e done. For the rest of the section a detailed look at the crnx of the coding, predicate rank/6 , is presented . Now begins a comprehensive study of the main predicate, rank/6. It begins with an introduction to the predicate and its purpose in this thesis followed by a presentation of the variables in t he argmnents and the snbrontines of rank/6 . Following this is a look at three of the more interesting tedmiqnes nsed in the body of the predicate; these indnde the use of recursion , the lmilt-in predicates bagof /3 aud setof /3 for all solutions, and the nse of ! and f ai 1 for control over the flow . The predicate rank/6 is nsed to approximate the rank of the algebraic operations of an algebra. The predicate rank (Homo, Sn, K, N, File, Rank) has six arguments, where Homo , Sn , K, N, and File are input and Rank is output. The argument Homo is itself a predi- cate representing the homomorphism in question, homomorphism (Rank, K, AlgB, AlgM, H) , which is a homomorphism. H. from the algebra AlgB to the algebra AlgM. Argument Sn is a positive integer that represents the power of the algebra AlgM for which AlgB is a subalgebra. The variable N is also a predetermined integer value which is an upper bonnd. The variable K is a finite, nonnegative integer representing the valne of I< in the Kth approximation of rank definition. Variable File is the file in which the database of alge- 33 braic oper ations on algebra AlgM with known rank are st ored . Finally, when a value for rank is approximated it binds wit h the variable Rank and is returned as output . When a homomorphism. H. of this model is of rank Rank, it represents the Kth approximat e rank, which satisfies nm} ,: (H) :::; Rank . A skelet al look at hmv the model approximates t he rank of an algebraic operation, using the Prolog notation of variables, follows. Given t he arguments homomorphism (Rank , K, AlgB , AlgM , H), Sn, N, and File. discussed above, the rank of homomorphism , H, is approximat ed through the following steps. For each nonnegative integer up to a fixed , finit e K, embed an algebra, AlgB , into au algebra called AlgBprime , by repeti t ion of K coordinat es for all p ossible rep eti tions. For each algebra, AlgBprime , a subalgebra of algebra, AlgM, to t he power of Sn+K , where homomorphism , Hprime , is t he extension of H, generate all algebras, AlgD , snd1 t hat AlgBprime is a subalgebra of AlgD , which is a subalgebra of AlgM to the power of Sn+K. For each algebra, AlgD , where Hprime lifts to AlgD, collect all possible sets. Y, of algebraic operations on AlgM wit h known rank, such that the size of each Y is less t han or eqnal t o N. Fnrthermore, for all AlgD , gener at e all algebras , AlgC , such that AlgBprime is a subalgebra of AlgC a subalgebra of AlgD . For each algebra, AlgC , find a set, Y. such t hat Y separat es AlgBprime and Y lifts to the factor algebra of AlgC wit h respect to Y, called AlgCmodY. The rank of homomorphism , H, is Rank, which is equal t o MaxRank+1 , where MaxRank is the rank of t he homomorphism, 34 g , with t he highest. rank iu the set of homomorphisms , Y. Beyond rank/6 , the body of code is nested seven predicates deep. Those predicates are rank/9 , for_each_k/9 , for_each_part/9 , for_each_D/8 , for_each_C/7 , there_exists_y /7 , and for_each_g/3. The rank is p assed thronghont t h e code as an accnmnlator pair of Rank and MaxRank, wh ere MaxRank chauges at the base case in for _each_g/3 , if the rank of any g is bigger than t he cnrrent MaxRank. Alt hongh we do not go into great detail for each predicate, we look at. the nses of recnrsion, bagof /3, and the cn t. Rank is defined recmsively on t he rank of simpler homomorphisms. Recursion is nsed in three ways thron ghon t the body of rank/6 . Implicit ly, as in the mathematical definition of rank. the nmk of a homomorphism, H, is based on the ranks of the homomorphisms , g , in the set, Y, where Tan /, : (H) :::; MaxRank+1 , snch t h at the rank of each gin Y is less than or eqnal to MaxRank. Explicitly, in predicate for_each_k/9 , recursion is nsed as a for loop for each I snd1 that 0 is less than or eqn al to I less than or eqn al to K. Furthermore, recursiou is nsed in predicates, for_each_part/9 , for_each_D/8 , for_each_C/7 , there_exists_Y /7 . and for_each_g/3 as a m eans of list traversal, with base case empty list for each . For the predicates for_each_D/8 and for_each_C/7 it is necessary to generate a list of all the appropriate snhalgebras, AlgD and AlgC , resp ectively. Mathematically, we are moving from qn antificatiou over algebras to qnantificat.iou over sn balgebras. Logically, we ar e moving from FOPL to higher-order predicate logic. To do this, the built-in predicate bagof /3 and the predicate subalgebra/3 specially written for t his thesis ar e 35 nsed. Predicate subalgebra (A, B, C) takes algebras A and C, where A is a snbalgebra of C, as inpnt, and finds an instance of an algebra which is a snbalgebra of C and has A as a snbalgebra, and hinds it to ontpnt variable, B. The bnil t-in predicate, bagof /3 , is of the form bagof(Template,Goal,List) . and is read as the list.. List , of all instances of Template satisfied by Goal. As an example, consider the casC' of generating all algebras, AlgD , snch that AlgBprime is a snbalgebra of AlgD. which is a snbalgebra of AlgM to the power of Sn+K. In order to do this, t he predicate for_each_part / 9, which is written % for_each_part(+PARTS,+HOMO,+ALG_B,+ALG_M,+ALG_MnK,+K,+N,+MAXR,-R) % If all partitions in the list argument, PARTS, are exhausted, % then argument, R, binds with MAXR, the maximum rank of % homomorphism, HOMO. Otherwise, recursively traverse list, PARTS, % to approximate the rank of homomorphism, HOMO . for_each_part ( [] , Homo , Alg_B,AlgJM,AlgJMnK,K,N,R,R). for_each_part([Part iParts] ,Homo,AlgJ3,AlgJM,Alg_MnK,K,N,MR,R) embed_B(Alg_B,Part,algebra(Bprm,FBprm)), list_to_ord_set(Bprm,OBprm), ord_f}JilCt ions (FBprm, OFBprm) , is_algebra(algebra(OBprm,OFBprm)), subalgebra(algebra(OBprm,OFBprm),Alg_MnK), make_hprime(Homo,algebra(OBprm,OFBprm),Hprm), is_homomorphism(homomorphism(R,K,algebra(OBprm,OFBprm),AlgJM,Hprm), bagof(Alg_D , subalgebra(algebra(OBprm,OFBprm),Alg_D,AlgJMnK),SubAlgsJD), ! , for_each_D(SubAlgs_D,Hprm,Alg_M,algebra(OBprm,OFBprm),K,N,MR,TR), for_each_part(Parts,Homo,Alg_B,AlgJM,Alg_MnK,K,N,TR,R). calls bagof /3 to generate the list, SubAlgs_D, of all the snbalgebras between an algebra, algebra(OBprm,OFBprm) . and algebra, AlgJMnK , by repeated calls to subalgebra/3. 36 For predicate there_exists_Y /7, a list of all possible sets, Y, of h omomorphisms, g , from algebra, AlgD, to algebra, AlgM, is needed. To accomplish this goal there is a call to predicate, get_Ys/5 , in t he body of for_each_D/8 . In get_Ys/5 , sh own below, there are two calls to set of /3 . T he built-in predicate set of /3 consists of a call to bagof /3 followed by a call to the lmil t-in predicate, sort/2. Predicate , sort/2 , sorts the list , List , from bagof /3 , and removes duplicate entries from the list, resulting in an ordered set. % get_Ys(+ALG_M,+ALG_MN,+K,+N,-LISTOFYS) % When using get_Ys/5, it is assumed that the database of algebraic % operations of an algebra, ALG_M, with known rank are asserted as % facts in the system . All instances of homomorphism/5 with % arguments K, ALG_M, and ALG_MN are collected in an ordered set. % The order of this set is based on the rank of the homomorphisms . % Reverse the order of this set then collect all instances of % sublists of the set in an ordered set . Each sublist is ordered % from maximum rank to minimum. Finally, remove all the sublists % that are strictly larger than N. get_Ys(M,Mn,K , N,Ys) : setof(homomorphism(R,K,Mn,M,H),homomorphism(R,K,Mn,M,H),Gs), reverse(Gs,RGs), setof(G,sublist(G,RGs),Zs), sizeof_g_lessthan_N(Zs,N,Ys). Here, the first call to set of /3 collects all t he homomorphisms from algebra Mn to algebra M, for some K, into a list , Gs . ordered by rank. The call to reverse/2 reverses the order of the list so that homomorphisms with maximum rank come first (i.e. decreasing order on rank). The built -in predicate sublist/2 maintains the order previously imposed on the original list , thus the second call to set of /3 generates all the lists, G, wh ere G is a sublist of Gs , and stores them as the ordered list of lists Zs . The order of Zs is increasing, based 37 on the ranks of t he first homomorphism in each snblist contained in Zs. Therefore, all the snblists containing homomorphisms with a maximnm of rank zero come first, followed by those with a maximnm of rank one, and so on. \iVhy do it like this? If there is a Y containing proj ections only, that separates AlgBprime and lifts to AlgCmodY , then it does not matter if a Y with a rank one homomorphism exists that does the same thing. \i\Tithin each loop. one wants t he minimnm rank possible. Why nse bagof /3 and set of /3 instead nsing the backtracking feature explicitly? Backtracking is t.ongh to C"outrol in t he cases mentioned above. There are cases within rank where WC' want a failure in a snb-routine to resnlt in a failure in of the main routine (discnsst>cl in t he next section). It is not so easy to differentiate between these failures when they occm on the same level of programming. By using the predicates mentioned , we make nse of backtracking explicitly by collecting all the solntions in a list and then nse recmsion to test each of the solutions. Next , we disC"nss the nse of the cut , ! /0 , fail/0 , and assert/1 , for control over the flow of the code. Au important asp ect of any compnter programming is control over the flow of the code. In particnlar , this means being able to prune fruitless branches from the search tree. This point becomes very apparent when coding the problem of approximating rank. Even for relatively small algebras, calculating the rank of their algebraic operations creates a large search tree in a short time. The reason for the rapid growth of the search tree is the potentially large number of snbalgebras generated. Recall , in the body of the predicate, rank/6 , t he generation of all subalgebras , AlgD , between 38 some algebra AlgBprime and algebra AlgMSnplusK is a necessity. Then , for each of those subalgebras, Prolog generates all the subalgebras , AlgC , between algebra AlgBprime and algebra AlgD. For this reason it is necessary to incorporate the built-in predicates , ! /0 and fail/0 , to trim the search tree. There are two types of <"nt nsed in Prolog, as discnssed by Richard O 'Keefe in his text, Th e Cm.ft of Prolog [16]. The two cuts in question are called red cuts and grue cuts. In simple terms , red cnts cause Prolog not to consider later clauses of a goal, while grne cuts keep Prolog from backtracking through the search tree unnecessarily, looking for other solutions. The predicate fail/0 , when used , canses Prolog to fail and initiate backtracking to find alternative solutions. Both types of cnt and the fail/0 are used in the body of the code of rank/6 , in order to control flow. For clarity, different placement points for the different cnts are used in the code of this research. Red cuts are placed at the end of a line, and grne cuts at the b eginning of a line. A presentation of three examples from t he code, one of the red cut, one of the grue cut , and one of the fail in conjunction with a cnt, is made next. Recall that t.he qnantification in the definition of rank consists in part of the statement that for all subalgebras, D , of algebra Mn+k and for all snbalgebras , C , of D , where h' lifts to D , there exists a set , Y , of homomorphisms from D toM snch that IYI : : ; N, h' lifts to C / Y , and rank (g Ic ) < n:, for all g E Y . In the code, this st atement is represented by the three predicates, for_each_D/8 , for_each_C/7 , and there_exists_Y /7 , each controlling the search tree in a different way. The first predicate, for_each_D/8 , represents the line, 39 ".. .for all subalgebras, D , of algebra, M n+k, and for all snbalgebras, C, of D, where h' lifts to D, ... ", aud is presented here. % for_each_D(+ALGS_D,+HPRIME,+ALG_M,+ALG_BPRIME,+K,+N,+MAXRANK,-RANK) % If all the subalgebras in the list, ALGS_D, are successfully % exhausted, RANK binds with argument, MAXRANK. Otherwise, % recursively traverse the list, ALGS_D, looking for only those % algebras in the list which the homomorphism, HPRIME, lift to . % Finally , if HPRIME does not lift to an algebra in the list, % ALGS_D, move on to the next algebra. for_each_D([] , Hprm,Alg_M,Alg_Bprm,K,N,R,R) . for_each_D([algebra(D,FD )j Alg_Ds] ,Hprm,AlgJM,Alg_Bprm,K,N,MR,R) list_to_ord_set(D,OD), ord_functions(FD,OFD), lifts(Hprm,algebra(OD,OFD),Alg_M), get_Ys(Alg_M,algebra (OD,OFD) , K, N,Ys), bagof(Alg_C,subalgebra(Alg_Bprm,Alg_C,algebra(OD,OFD)) , SubAlgs_C), ! , for_each_C(SubAlgs_C,Hprm,Alg_M,Alg_Bprm,Ys,MR,TR), for_each_D (Alg_Ds,Hprm,Alg_M,Alg_Bprm,K,N,TR,R) . for_each_D([Alg_D jAlg_Ds] ,Hprm,AlgJM,Alg_Bprm,K,N,MR,R) for_each_D (Alg_Ds ,Hprm , Alg_M,Alg_Bprm,K,N,MR , R). The cut appears at the beginning of the sixth line, in the tail of the second clause. In t his case, if the call to predicate, lifts(Hprm,algebra(OD,OFD) ,Alg_M) , fails , then Prolog proceeds to t he third danse of for_each_D/8 and moves on to the next algebra, Alg_D, in the list. However, if lifts(Hprm,algebra(OD,OFD ) ,Alg_M) succeeds, followed by a fail in predicate, for_each_C/7 , then for_each_D/8 will fail also. That is, Prolog will not search any fnrther algebras, Alg_D , in the list, as well as not move back to previously searched algebras, by prnning all fntnre solntions and proofs of t he qnery. The predicate for_each_C/7 consists of two danses which traverse the list of snbalgebras, C , passing each to there_exists_Y/ 7 for testing. In the case of for_each_C/7 , 40 if there_exists_y /7 fails on any given C , then no fnrther solutions to the query exist. Here one does not want Prolog to backtrack to a previous subalgebra, C , and try again. The placement of a cut, in the second clause, in front of the call to there_exists_Y /7 , achieves this goal by prnning the search tree of any other proofs. % for_each_C(+ALGS_C,+HPRIME,+ALG_M,+ALG_BPRIME,+YS,+MAXRANK,-RANK) % If all subalgebras in the list, ALGS_C, are successfully % exhausted, RANK binds with the maximum rank, MAXRANK. Otherwise, % recursively traverse the list, ALGS_C. for_each_C([] ,Hprm,Alg_M,Alg_Bprm,Ys,R,R). for_each_C([algebra(C , FC )J Alg_Cs] ,Hprm,Alg_M,Alg_Bprm,Ys,MR,R) list_to_ord_set(C , OC ) , ord_functions(FC,OFC), ! , there_exi sts_Y(Ys,algebra(OC,OFC),AlgJM,Alg_Bprm,Hprm,MR,TR), for_each_C(Alg_Cs,Hprm,Alg_M,Alg_Bprm,Ys,TR,R) . For t he fin al predicate, there_exists_Y /7 , one wants to test each set, Y , until Prolog succeeds or the sets Y are exhausted. Once Prolog finds a Y that succeeds the search may continue on to the next C . If all the choices for Y fail , then the entire search must fail. To accomplish this, a cut is placed before a call to fail/0 , in the first danse. This clause is the base case for this predicate and it indicates that Prolog has reached the end of the list withont finding a solntion to this branch of the search tree. So, Prolog is forced to fail in order to back out of the query. % there_exists_Y(+YS,+ALG_C,+ALGJM,+ALG_BPRIME,+HPRIME,+RANK,-NEWRANK) % Recursively traverse the list argument, YS, of sets of % homomorphisms with known rank, searching for a set which % % % % satisfies all the predicates in the tail of the second clause . If a set does not satisfy all the predicates, move on to the next set using the third clause. If no such set exists, cause a fail of the whole predicate by the first clause . 41 there_exists_Y ( [] ,Alg_C,Alg_M,Alg_Bprm,Hprm,R,NewR) :- ! , fail. there_exists_Y ( [Y /Ys] ,Alg_C,Alg_M,Alg_Bprm , Hprm,R,NewR) separates (Y,Alg_Bprm , Fact_Alg) , factor_algebra(Alg_C,Y,Alg_Bprm,Fact_Alg,algebra(CmodY,FCmodY)), list_to_ord_set(CmodY,OCmodY), ord_functions (FCmodY,OFCmodY), is_algebra ( algebra(OCmodY,OFCmodY)), lifts(Hprm,algebra(OCmodY,OFCmodY) , Alg_M), for_each_g(Y,R,NewR) . there_exists_Y([Y /Ys] ,Alg_C,Alg_M , Alg_Bprm,Hprm , R,NewR) there_e x ists_Y (Ys , Alg_C,Alg_M,Alg_Bprm,Hprm,R,NewR) . This con d n des om look at the main predicate of t he research , rank/6 . To view rank/6 in its ent irety consnl t Appendix B . T he appendix also contains t he rest of t h e code written to facilitate the approximation of rank. These inclnde; make_M_to_the...n/3 , for gen erating power algebras; subalgebra/3, subalgebra/2 , an d gen_subalgebra/3 , for testing and creating snbalgehras; homomorphism/4 , for testing and creating h om om orphism s, as well as extending p artial hom omorphisms; partition_k/3, for nse in genera ting all th e embeddings of an algebra; embed_B/3 , for embedding by repetit ion of coordinates; lifts/3 , to test for lifting of a homomorphism ; separates/3 , to test for sep aration of an algebra; factor_algebra/5 , for generating a factor algebra; make_projections/4 , described ab ove; and a h andful of tools nsed sp ecifically hy t h e predicat es above or sh ared by a few. The last t hing needed to be done in t he presentation of t h e computation al m odel is a complexity an alysis of t he program. 42 2.4 Complexity Analysis To analyze the code written for the approximation of rank we use a method called Big-Oh analysis. The definition, T (n) = 0 (! (n)) if there are constants c and n 0 such that T (n)::::; cf (n) when n 2: n 0 , is given by Mark Allen Weiss in his text , Data StnJ.ChLr-es and Algor-ithm Analysis in C++ [21]. Complexity analysis is done on time and space related issues. In this thesis it is done on the running times of the code. The reason for this choice is discussed fnrther on in this section but it is enough to mention here that time and space for the research are closely related due to the lists of subalgebras generated while calculating rank. Fnrthermore, space complexity is always bounded by time complexity. Some useful rules of Big-Oh analysis that are used in the analysis of the research are as follows. To calculate the running time of a predicate that loops , multiply the number of iterations of the loop by the running time of the statements in the tail of the predicate. The running time of nested predicates is the rnnning time of the innermost predicate multiplied by the number of iterations of each outside predicate. The running time of consecutive statements in the tail of a predicate is equal to the maximum running time of each of the statements. The nmti.me of a predicate with multiple clauses is the runtime of the test of the clause, times the maximum running time of the statements inside the clauses. Because of the lack of a priori knowledge of the number of subalgebras of any given algebra, the analysis in 43 this stndy is of the worst-case scenarios. The nnmber of snbalgebras of a given algebra is bounded by the nmnber of snbsets of the nnderlying set of the algebra. Thus , for the purposes of this research the worst-case scenario is when every subset of an algebra represents a snbalgebra. This section presents the variables nsed in the complexity analysis of the code as well as a table consisting of each predicate and its Big-Oh analysis. Following this is an explanation of t he resnlts of the analysis done on predicates make_projections/4 and rank/6. This se(-t.ion conclndes with a discnssion of the nse of the worst-case scenario and the time versns space issnes. The variables nsed in the complexity analysis are based on the inpnt variables of the predicate, rank/6. The approximation of the rank of an algebraic operation, h, on an algebra M , assmnes the inpnt of the following ; a positive integer , n; a snbalgebra, B , of algebra, M '"; a nonnegative integer , k; and a positive integer , N. Let IMI = m, the number of elements in the algebra, M , then, it follows that the size of Mn is mn and the size of B is also mn , in the worst-case. Furthermore, let l represent the nnmber of functions in the function list of the algebra, M. Table 2.1 contains the names of varions predicates and their Big-Oh analysis. The database of projections , which have rank 0, is created nsmg the predicate, make_projections/4. This predicate generates the database, given an algebra, M , of all the proj ections from M 1 to M for I ::; K. Let IMI = m and let K = n + k, where n is a positive integer and k is a nonnegative integer. To determine the com- 44 II Complexity Analysis Predicate embed/3 factor_algebra/5 gen_subalgebra/3 Complexity 0 (n2 · 1.: · rn") 0 (N · m 2(n+k )) 0 (z. m3(n+k)) Predicate get_Ys/4 homomorphism/4 lifts/3 Complexity 0 2n 0 (z. m4 (n+k+ I ) ) 0 (z. m4(n+k+l)) Predicate make_hprime/ 4 make_projections/4 ord_functions/2 Complexity 0 (m. 0 ((n + !.l· m ." +k. 2m"+'-) 0 (l) Predicate parti tion_k/3 separates/3 subalgebra/2 Complexity O( 0 (N. m .2(n+k )) 0 (z. m2(n+k)) ( n+!) 1 11 "' ) (h+n-J )I ) (n-l )!·(k -1) 1 Table 2.1: Big-Oh analysis on selected predicates. plexity of make _projections/4 , note that it consists of five nested loops, for_each_i/4 , for_each_sub/4 . for_each _j/5, projections/3, and proj/3, listed from outer most to inner most. Therefore, the rnnning time of make _projections/4 , is at most the running t ime of pro j /3 times the number of iterations of each of t he outside predicates , for_each_i/4 , for_each_sub/4 , for_each_j/5 , and projections/3 . The function of proj (J ,Element ,P) is to fiud the J th projection , P, where J is between 0 and n + k, of Element , an element of M n+k. Referring to the rode for pro j /3 b elow , the Jth projection of Element is found by traversing t he list, Element , to the J th position and binding the element t here with variable, P. % proj(+N,+ELEMENT,-P) % The argument, ELEMENT, is instantiated with an element list. If % the integer, N, is strictly larger than the size of the list, 45 % % ELEMENT, then proj/3 fails. Otherwise, argument, P, binds with the Nth projection of an element, ELEMENT. proj(N,[],P) :- 1, fail. proj (1, [X!Rest] , [X]). proj(N, [X !Rest] ,P) : N1 is N-1, proj(Nl,Rest,P) . The cost of doing this is the cost of traversing the entire list, which is of size, n + k, in the worst-case. Vvorking onr w<-1.y from inside ont , the nmnher of iterations of project ions/3 is eqnal to the nnmher of elements in the algebra M ; where i is greater than or equal to zero and less than or eqn al ton+ k:. Thns, at the worst-case, jMil = mn+k, making the number of iterations also m 11 +k . For both , for_each_i/4 and for_each_j/5 , the nnmber of iterations is at most n + k:. The predicate f or_each_sub/ 4 traverses a list of all snbalgebras of algebra, M ;, where i is at most n + k:. There are at most 2mn+k - 1 possible snbalgehras of M ;. therefore as many iterations of f or_each_sub/ 4. The empty set does not make a snbalgebra in onr view, thns we snbtrac.t 1, the case that none of the elements are in the snhalgebra. Therefore, make_pro j ections/ 4 h as a running time of at most t · 2 "+'" ( n + 1.:) · m!" +k· · (n + 1.: ') ( 171 - 1) , or T (n . h:, rn) 0 ((n + k:) · mn+k · (n + h/ · (2mn+k)) 0 ( (n + kl . TT/,n+k . (2m"+' )) . 46 The analysis of the predicate rank/6 is similar to that of make_projections/4 in that rank/6 consists of nested predicates also, with the inner most predicate for_each_g/3 . Thus, the running time of rank/6 is at most the running time of for_each_g/3 times the number of iterations of each of the predicates, there_exists_y/7, for_each_C/7 , for_each_D/8 , for_each_part/9, and for_each_k/8 . The cost of running for_each_g/3 is equal to one times the cost of traversing a given list of homomorphisms, Y. The size of Y is at most N , a predetermined integer value. So, the nmning time of for_each_g/3 is at most N. The number of iterations of there_exists_y /7 is at most the cost of traversing a list of all the possible snblists of homomorphisms from an algebra, M n+k to algebra, M . The unmber of possible homomorphisms from Mn+k to M , is mm"+k, since there are m choices for each of the mn+k elements of Mn+k. Again, this is a worst-case scenario since it is not always true that all these possibilities make a homomorphism. To get the number of snblists of this list of all the homomorphisms, note that either each homomorphism is in a snblist or it is not , thus there are two choices for each. Assuming, in the worst-case, that N is greater than or eqnal to mm" +" then the number of sublists is ~ at most 2m"' +k . Both the predicates, for_each_C/7 and for _each_D/8 , traverse a list of snbalgebras with an eqnal maximum size. The maximnm nnmber of snbalgebras in the list is equal to the maximum number of subalgebras of an algebra, Mn+k. The algebra M n+k contains m n+k elements, each of which has two possibilities, either it is in any given subalgebra or it is not. Thns the maximum number of subalgebras is 2mn+k - 1. The number of iterations of the predicate for_each_part/9 is equal to the number of 47 ways of partitioning an integer k into a list of size n, which eqnals /. : + n- 1 ( n- 1 ) Finally, the predicate, for_each_k/8 , is really jnst a for loop from 0 to some k , where k is a nonnegative integer. Tlms f or_each_k/8 consists of J.: + 1 (becanse we start at zero) iterations . Therefore, t he rmming time of rank/6 is eqnal to T (n, k ,m, N) o(N2'""'"+' (2"'"., -1) (2m"+' -1) ( /. :+n - 1 n -1 ~ (k+l)) ) . (2m"+>)'. 2"'"'"+>) in the worst-case scenario. It is worth taking the time right now to investigate the nse of t he worst-case scenario thronghont the complexity analysis for this research. In some instances the number of snbalgebras is grossly over estimated. It is assumed that it is the case that every subset of an algebra represents the underlying universe of a subalgebra of the algebra. In practice, the number of subsets that are actually subalgebras may vary greatly from algebra to algebra. In fact , in some cases there will be only one snbalgebra. Let us look at two examples which show both ends of the range. Let M 0 and M 12 be the three-element, mono-unary algebras given in Figme 2-3. 48 (a) M 9 b (b) M12 h (/, Lt • Lt a \.{ Lto Figure 2-3: Algebras M 9 and M 12 . The algebra, M 9 , has seven snbalgebras, that is , one for every subset of the set {0, a, b} minus the empty set. , whereas, algebra, M 12 , has only one subalgebra, which is the algebra itself. Furthermore, in analyzing rank/6 , we assume the list of all possible sub lists of homomorphisms from an algebra, Mn+k , t.o algebra, M , is of size, 2m mn+k This number also represents a possibly huge over estimation. As a matter of fact, there are three assumptions made in arriving at this figure which take the worst-case into account. First , that all possible mappings from one algebra to another are actually homomorphisms. Second, that all those homomorphisms appear in the database with a value for their rank. The third assumption is that the boundary, N, is larger than the number of homomorphisms. That is, that we do indeed want all the sublists, not a bounded number of them. So our complexity analysis overestimates our actual running times in most cases, hnt their is no alternative here without prior knowledge of the number of subalgebras of an algebra or the number of homomorphisms. The space costs thronghout the code is bounded by the expected time costs. That is, the time needed to consider all C :::; D is proportional to the number of C times the number of D , whereas the space required is proportional to the number of D plus the 49 largest number of C. The time complexity is strongly dependent on the time it takes to generate and test all the possible snbalgebras for each rnn of the code. Similarly, the space complexity is based on the amount of memory that is spent on storing all the possible subalgehras dnring a given rnn. Thus , it is acceptable to restrict the analysis to one case. 2.5 Summary To summarize, the presentation of the computational model consists of fonr distinct steps. The first breaks the problem dowu into an experimental design, in which the obstacles of programming particular problems are defined . The second step justifies the choice of programming language and discusses the languages m erits with respect to the problem. The third step discusses the implementation of the code; that is, the creation of the computational model. Finally, the fonrth step analyzes the complexity of the code. 50 Chapter 3 Results and Discussion 3.0 Introduction Chapter 3 presents an analysis of the results obtained through running the computational model introduced in Chapter 2. This includes a study of the runtimes of the predicate, make_projections/4, for a few mono-unary and bi-unary algebras. The results and runtimes of r ank/6 , are also discussed. The running of rank/6 gives two types of results for analysis , timing and approximations of the rank. This thesis looks at mono-unary and bi-unary algebras specifically, with the mono-nnary algebras labelled as Mi and the bi-nnary algebras labelled P j, where i and j are finite positive integers greater or equal to one. The results are presented in a series of tables, accompanied by figures which give a representation of the relevant algebras. 51 3.1 make _projections/4 Recall from Chapter 2, the worst-case time complexity of the four argument predicate, make_pro jections/4, is T (m , k:) = 0 (h: 3 · mk ·(2m')) , where m is the size of a given algebra, say M , and k is the power of an algebra, say B , where B ::; Mn. T (m , k) = 0 (f (m , k) ), where f (m , k:) = k 3 · mk · That is, (2m') . This section looks at the actual times of running make_pro j e ct ions/ 4 on some mono-unary and bi-unary algebras of size up to and including m = 4. The times are presented in tables followed by a discussion of the findings of the author. The times in the tables represent a cumulative figure, that is , the runtime of make_pr o j e ct ions/ 4 for some particular k: , is the runtimes for each i , where i = 1, 2 . . .. , h:. Times presented in the tables are based on an average over one hundred rnns except where marked by an asterisk , *, which are taken from the time of one rnn. The times represent CPU time and are given in milliseconds (ms) as reported by the SICStus Prolog interpreter. Figure 3-1 contains a pictorial representation of the one-element algebras , M 2 and P 2, where M 2 is mono-unary and P 2 bi-unary. As far as algebras are concerned, these two are rather uninteresting on their own. For the sake of looking at the complexity analysis though, with these two algebras the worst-case is the only case. That is, there exists one subalgebra for each power algebra, which is the worst-case scenario. Given that m = 1 for these algebras, the complexity is simplified to 52 0 ~ ~ Figure 3-1: Algebras M 2 and P 2. So, for m = 1, f (m , 1.:) = f (1, k) = k 3 . Table 3.1 contains the observed rnnning time of the predicate, make_projections/4 , on the two one-element algebras, for various values of J.: . Notice that the CPU time for rnnning the predicate on algebra, P 2 , is slightly larger than that of the times of running on algebra, M 2 . The only difference between these two algebras is that P 2 has one more function than M 2 , but the analysis suggests that the running time of the predicate is independent of the number of functions in the algebra. Also presented is a column containing the CPU times for P 2 divided by the times for M 2 , to compare the growth rate of the two. From these numbers , P 2 is approximately 1.35 times slower than M 2 , for k = 10, 25 , 50, 75 , 100, 200, which would suggest there is a constant difference between the growth rates. This may be explained by the original analysis work. Recall, in doing the complexity analysis , constants are ignored, the important part is the comparative growth rates. One way to test the validity of Big-Oh analysis is to divide the actual running time of a predicate by the estimated rnnning time. For example, given that a predicate's running time, T (n) , has been analyzed as being 0 (f (n)) , for some function, f (n) , divide T (n) by f (n) for a range of n. If the computed values converge to a positive constant, then f (n) is a good estimate for the rnnning time . Also , if f.he values converge to zero, then 53 k Time (M2) Time (P 2) Time (P 2/M 2) Time (M 2) / k3 Time(P 2) / k3 1 0.5 1.2 2.4 0.50000 1.20000 2 1.8 2.4 1.33 0.22500 0.30000 3 3.7 5.4 1.46 0.13704 0.20000 4 6.2 8.2 1.32 0.09688 0.12813 5 9.4 12.8 1.36 0.07520 0.10240 10 42.5 55.7 1.31 0.04250 0.05570 25 404.6 538.9 1.33 0.02589 0.03449 50 2609.1 3495.5 1.34 0.02087 0.02796 75 8013.7 10932.7 1.36 0.01900 0.02591 100 18269.0 24955.4 1.37 0.01827 0.02496 200 137840.0 187957.9 1.36 0.01723 0.02349 (rns ) (rns ) Table 3.1: Running times aud complexity of make_projections/4 on algebras M 2 and P 2 . Size m = 1. Only 1 subalgebra for each k. f (n) is an over-estimate for the running time, but still an acceptable one. Where as , if the values diverge, the estimate for the running time, f (n) , is an under-estimate and should be re-evaluated. In the case of algebras , M 2 and P 2 , the generic runnmg time of the predicate, make_projections/4, is estimated to b e 0 (k 3 ). The values derived from dividing the actual CPU times of rnnniug the predicate, for various k, by k3 are recorded in the last two columns of Table 3.1. The calculated values are converging towards zero at a slow 54 rate, which suggests the use of k 3 is a good although slight over-estimate. Furthermore, recall that the case of m = 1 represents one of the examples where all possibilities are explored, i.e. all the snblists exist as snbalgebras, which suggests that the estimate for the running time, 0 (') · rnk · (2mk)) , of predicate, make_projections/4 , is an acceptable estimate. The diagrams contained in the fignres, Fignre 3-2 , Fignre 3-3, and Fignre 3-4, represent all the 2-element mono-unary and bi-unary algebras, np to isomorphism. The estimate of the running time of make_pro j ections/ 4, on these algebras is 2k)) , T(m,k) = T(2,k:) = O(J(2 , k)) = 0 ( k 3 · 2k · ( 2 for finite nonnegative integer, k:. For each of these algebras, the time (in milliseconds), the number of subalgebras (SA) , and the times divided by f (2 , k), for each k, are recorded in Table 3.2 and Table 3.3. It can bee seen in both tables the runtimes grow quickly as the value of k goes from 1 to 4. From the function , f (2 , k) , it is expected that the runtimes are strongly dependent on k. The times grow so quickly because of the 22 k - 1 sublists which must be tested for each k. Within each k , it is shown that the runtimes are strongly dependent on the actual number of these sublists which are subuniverses. For algebras. M 3, M 4 . P 3, P 4 , P 5 , and P 7 , the predicate, make_projections/4, was run for k such that 1 ::::; k: ::::; 3. The runtime data which corresponds with these algebras are recorded in Table 3.2. Again, it is dear that the values of Time/ f seem to be converging toward zero , which suggests T (2, k) = 0 (J (2, k)) is an overestimation. 55 Fignre 3-2: Algebras M 3, M 4 , and M 5 . (a) P :3 (b) p 4 ,-, il 1 r.- l-:D 0 ~ f1 1 (c) P 5 (d) p 6 t Jt1 1::-t] 0 Fignre 3-3 : Algebras P 3 , P 4 , P :; , and P 6 . do In each case, the number of possible subalgebras , i.e. the number of sublists, is equal to (2 2 k - 1) , for /,: = 1, 2, 3. That is , 3 possible subalgebras when k = 1, 15 possible subalgebras when /,; = 2, and 255 possible subalgebras when k = 3. Only two of the six algebras of this table ad.nally reach the worst-cases mentioned above, and these two grow the quickest. It can be seen from the table that the major contributing factor to the actual CPU runtime of make_projections/4 , for each k , is the number of subalgebras the algebra has. Those algebras that have more snbal,e;ebras have runtimes which grow noticeably faster. 56 (b) P 8 (c) P 9 P1 It do ~ Figm e 3-4: Algebras P 7 , P 8 , and P 9 . p3 M4 M3 Algebra k Time SA Time/ f Time SA Time/ f Time SA Time/ f 1 1.8 2 .2250 2.2 3 .2750 2.3 2 .2875 2 16. 1 8 .0314 26 .1 15 .0510 21.9 8 .0428 3 590.4 128 .0107 1070.5 255 .0194 807.4 128 .0146 p4 Algebra p7 Ps k Time SA Time/ f Time SA Time/ f Time SA Time/ f 1 1.5 1 .1875 2.7 2 .3375 3.0 3 .3750 2 13.3 4 .0260 21.3 8 .0416 34. 7 15 .0678 3 455.3 64 .0082 810.8 128 .0147 1448. 7 255 .0262 Table 3.2: Times to nm rnake_projections/4 on algebras of size m = 2, for 1 :::;; k:::;; 3. The dat a for the rest of t he two-element algebras, M 5 , P 6 , P 8 , and P 9 , appear in Table 3.3. In t he case of t hese fom algebras, t he predicate is rnn for t he values of k = 1, 2, 3, and 4. When J.. : = 4, t he worst-case number of suhalgebras expected is 65535. This number is far greater than the nmnbers encountered by these algebr as, as seen in the t able. This would explain t he rather qnick convergence to zero, demonstrated in all these 57 cases. Algebra p6 Ms k Time SA Time/ f Time SA Time/ f 1 0.9 1 .1125 1.5 1 .1875 2 7.3 3 .0143 8.4 2 .0164 3 93.0 15 .0017 96 .0 8 .0017 4 14722.7 255 .0002 21962.2 128 .0003 Algebra Pg Ps k Time SA Time/ f Time SA Time/ f 1 1.6 1 .2000 1.2 1 .1500 2 10.4 3 .0203 10.3 3 .0201 3 134.0 15 .0024 133.4 15 .0024 4 25554.3 255 .0004 25137.8 255 .0004 Table 3.3: Times to nm make_projections/4 on algebras of size m = 2, for 1 :S k :S 4. The three-element algebras looked at in this thesis are found in Figures 3-5 , 3-6, and 3-7. These include all the three-element mono-unary algebras, M i for 6 :S i :::; 12, up to isomorphism, and three chosen three-element bi-unary algebras, P 1 , P 10 , and Pn. So, when m = 3, the function , f (m , k:) , becomes 58 (c) M 8 b (/, b a a Figure 3-5: Algebras M 6 , M 7 , and M 8 . (a) M 9 h a cj cj cjO (c) M 11 (b) M10 a b • • cjO h a \!{ Fignre 3-6: Algebras M 9 , M 10 , and M 11 . For all the three-element algebras, with the exception of algebra M 12 , it is possible to run make _projections/4 for values k = 1 and 2, only. The runtimes , for each k, on these algebras are found in Table 3.4, along with the number of subalgebras generated at each level and the results of the complexity test. Again it can be seen, even for just two values of k, the consistent rapid growth rate in runtime from h: = 1 to k = 2. Furthermore, the table shows that there is a definite correlation between the number of subalgebras in a run and the time cost of that run, for each k. 59 Algebra M1 M6 MB k Time SA T ime/f Time SA Time/f Time SA Time/ f 1 3.8 4 .1583 3.1 3 .1292 4.4 5 .1833 2 815.4 256 .0221 277.2 75 .0075 518.1 161 .0141 Algebra Mw M0 Mn k Time SA Time/f Time SA Time/f Time SA Time/f 1 5.7 7 .2375 3.3 3 .1375 2.5 2 .1042 2 1515.3 511 .0412 145.0 31 .0039 192.5 44 .0052 pl Algebra Pw Pn k Time SA Time/ f Time SA Time/f Time SA Time/f 1 2.2 1 .0917 4.4 3 .1833 2.9 2 .1208 2 127.2 9 .0035 278.4 48 .0076 140.2 13 .0038 Table 3.4: Times to rnn make_projections/4 on algebras of size m = 3, for 1 ::; k::; 2. (b) P w b a (c) P n 9b ~a t;Jb ~a (d) p l ,Jb 0 ~0 I- ti 'b f. rIt a do Figure 3-7: Algebras M 12 , P w, P n, and P 1 . The algebra, M 12 , is the only three-element algebra for which it is possible to make a nm for values of k: up to and including 3. Table 3.5 contains the runtime data collected for this algebra. Here it can be seen that the values in t,he Time/ f column converge very . 60 quickly toward zero, although the runtime for k = 3 is comparatively large. In fact, this particular nm took 41,800.470 milliseconds, which is approximately eleven and a half hours. This gives further evidence that the size of k has a strong influence on runtime even though the fnnction nsed for the Big-Oh analysis is a large over-estimate. Algebra M12 k Time SA Time/f 1 1.6 1 .0667 2 73.5 7 .0020 41800470* 511 .0004 ') v Table 3.5: Times to rnn make_projections/4 on algebra, M 12 , of size, m = 3, for 1 ::; k ::; 3. Two four-elem ent algebras are stndied in the research, one mono-unary and one biunary. Both algebras, M 1 and P 12 , are represented in Figure 3-8. The results of the runs done on these algebras are recorded in Table 3.6. The same observations apply to these resqlts, that is , the bigger the k:, the longer the run, and the more subalgebras for each k, the longer the run . In both cases we can clearly see the increase in runtime from k = 1 to k = 2. Also , in the case of algebra M 1 for A: = 2, the nnmber of snbalgebras is substantially larger than for algebra P 12 . This difference is reflected in the disparity between the runtimes of the two. 61 c ,-, Te- C Hb n~ a ~ Fignre 3-8: Algebras M 1 , and P 12. Algebra M1 pl2 k Time SA Time/ f Time SA Time/ f 1 6.4 6 .1000 3.7 1 .0578 2 45285.0 7776 .0027 18095.5 16 .0011 Table 3.6: Times to run make_projections/4 on algebras of size, m = 4, for 1 ::::; k::::; 2. It can also b e seen throughout all the tables that the runtimes grow faster from one value of k to another as the size of the algebra, m , increases. Table 3. 7 contains the runtimes of predicate, make_projections/4, averaged over all the algebras of size m, for each value of k. We see from this table that the times grow rapidly as both m and k increase by increments of one. This can be attributed to the increase in the number of ,_ snblists tested , 2m - 1, for each case. This number also grows very rapidly as either m or k , or both, increase. 62 I k I m 1 2 3 4 1 .85 2.1 4.55 7.2 2 1.87 16.98 563.95 21844.25 3 3.39 408.28 41800470* NA 4 5.05 31690.25 NA NA TaNe 3.7: Average run times over 1 :::; m.:::; 4, and 1 :::; k:::; 4. What do these timing results suggest? The fact that m and k affect the time so strongly was expected from the complexity analysis . It is obvious that the number of sublists grows rapidly dependent on both m. and k , from the value of 2m.k -1. What is not so obvious from the complexity analysis is the effect the actual number of subalgebras would have on the runtime. The number of subalgebras that need to be looked at can not be changed, thus their affect on the runtime can not be helped. But, the influence of k and m may be lesseued, by finding a way of eliminating the testing of a sublist which does not geuerate a subuniverse. In other words , there may be a way to make the program smarter and thus allow for the predicate to b e nm on greater values of k in a reasonable amount of time. It is necessary to point ont why only small values of 1.: are looked at. Occasionally during a run, the execution error , "aborted: out of address space", is reported by SICStus 3 Prolog. In the case of running make_projections/4 on the two-element algebras, M 3 and M 4 (Figure 3-2 (a) and (b)), fork= 4, the execution error is reported after 179,470 63 and 189, 110 milliseconds , respectively. In contrast , for the two-element algebras Ms (Figure 3-2 (c)) , P 6 (Figure 3-3 (d)) , P 8 , and P 9 (Figure 3-4 (b) and (c)), it is possible to run make_projections/4 for valnes of k np to and indnding k = 4 (Table 3.3). Similarly, running on the three-element algebra, P 1 (Figure 3-7 (d)), for k = 3, invokes an execntion error after 66. 380, 390 milliseconds, or approximately 18.44 hours, whereas, the three-element algebra, M 12 (Figure 3-7 (a)) , sncceeds in creating the projections for k = 3 in approximately ll.GO homs (Table 3.5). The significance of these nnmbers lies in the nnmber of snhalgebras generated and their infinence on space costs. Regardless of the time it takes to perform a particnlar nm , the valne of k reached is dependent on the number of snbalgebras that are generated and stored in the search tree for later use. In theory, this snggests that given the appropriate amonnt of space, we would be able to run the predicate for any finite k in a finite time. In practice, we have seen from the timing resnlts that in cases of k greater than or eqnal to 4, t he potential runtimes are unrealistic, and trimming these runtimes is unlikely, nnless we have apriori knowledge of potential snbalgebras. Lessening the space costs is a more realistic goal. Some ideas -;::-':-"· for reducing space costs are presented in Chapter 4, in the fntnre work section. These indude asserting snbalgebras as atoms and the nse of relational databases for storage of homomorphisms and snbalgebras. 64 3.2 rank/6 In this section, the results of rnnning the predicate, rank/6 , are discussed. Recall , rank/6 is used to approximate the rank of an algebraic operation on some unary algebra, M. As discussed in Chapter 2. the arguments necessary to this predicate are, h : B --+ M , an algebraic operation of M , some nonnegative integer, n , such that algebra, B :::; M n, and B = > B' :::; M "+k, for some k, a positive fixed integer, and N, a bound for the number of homomorphisms to be used to separate B ' . The remaining two arguments represent a filename for a particular database and the approximated value of the rank of h, respectively. There are a total of twenty-four algebras looked at in the research, twelve mono-unary algebras denoted by M i, and twelve bi-unary algebras denoted by P i, where i = 1, 2, .. . , 12. The subalgebras generated for each algebra are denoted by B ij, where i is as above and denotes the algebra, and j is a counter on the number of subalgebras generated. For each of twenty-two of the twenty-four algebras 1 , rank/6 is run on all the algebraic operations where n = 1, for N = 1 and the values of k compatible with the database for the algebra. For the bi-unary algebras P 1 , P 4 , P 10 , Pn , and P 12 , the predicate was run on a few algebraic operations where n = 2, the reasoning for this is discussed below. The resulting ranks and runtimes are presented in tables in Appendix A along with the values of n , k: , and N where applicable. The runtimes reported in the tables are in milliseconds (ms). Note that Pro log rounds the times off to ten milliseconds, 1 Both the one element algebras are ignored because the only algebraic operations of each are the projections, which have rank less than or equal to 0. 65 so a time of zero means that particnlar nm took less than five milliseconds. Also , the times recorded for nnming rank/6 are based on single runs . Next, a brief discnssion of the runtimes is given followed by a look at some of the more interesting results obtained. The worst-case time complexity of rank/6 is k+n-1 n-1 where m is the size of the given algebra, n a fixed nonnegative integer, k a positive integer, and N a fixed finite bonnd. It can be seen that the worst-case time complexity is highly dependent on the nmnber of snbalgebras, similar to the worst-case time complexity of predicate, make_projections / 4. The relative growth rates in adnal runtime for both predicates validate this complexity. With this being the case, an in-depth look at the rnntimes of rank/ 6 is not necessary and one may refer to the previous section for a comparable discnssion. On the other hand, there are a few particular ontcomes that need to be addressed here. The first point is on a change in efficiency that was made in the midst of doing the rank simnlations. The runtime resnlts of the first three algebras , M 1 , M 3 , and M 4 , are noticeably less efficient than those of the rest of the algebras dne to adjnstments made to the code. After M 1 , M 1 , and M 4 were rnn, some improvements in code efficiency were made, which in turn changed the adnal runtime efficiency. For instance, the first dause of the predicate, subalgebra/3, was added, which stops the model from generat- 66 ing unnecessary subalgehras in the case where the only subalgebra is the algebra itself. Exactly three other snch changes were made, which is reflected in the faster runtimes for the later algebras. The important point is that the relative growth rates and the rank results were nnaffected. h• I c • •a. \fa Fignre 3-9: (a) The algebra M 1 and (b) the algebra P 1 . The next two points arise from the runs done on the fonr-element mono-unary algebra, M 1 , shown in Fignre 3-9. First of all , it is possible to rnn rank/6 on M 1 for n + k = 1 only, althongh the database contains projections for n + k = 2. This restriction is due to 2 Prolog address space constraints which are exceeded becanse algebra, (Ml) , has 7776 distinct snbalgebras each of which are generated a possible 7776 times in the worstcase scena,r.jo. When running rank/6 on M 1 for n + h: = 2, the error message "out of address space" is reported. This error is denoted in the tables by the acronym, OAS. For all the other algebras the rnns are bonnded only by the previonsly created database of projections. Now consider the snbalgebras , B 15 and B 16, with nniverse {O,a} and {O ,a,b}, respectively, whose resnlts are fonnd in Table 3.8 and Table 3.9. The letters, NA, denote that the rank is not available because it conld not be estimated dne to Prolog address 67 space constraints. The nmtimes are noticeably shorter when the elem ent a , in algebra B 15 or B 16 , is sent to element bin algebra M 1 . The difference in these runtimes is further confirmation that the nnmber of snbalgebras generat ed in the search strongly affects the efficiency of the code. In the cases where a is sent t o b, there are fewer snbalgebras, D :::; M n+k , for which t he homomorphism , h' , lifts to D becanse of the restriction that the element , c E M 1 . satisfies f (c) = a. Since there are fewer snbalgebras to b e searched, the runtimes are fas ter for these homomorphisms as opposed to the homomorphisms in which a is sent to 0. Subalgebra Homomorphism k Rank (:S) Time (ms) ~ :S M 1 !1 (0) = h (a) = 0 0 1 142680 1 NA OAS h (0) = 0, h (a) = a 0 0 0 1 0 0 h (O) = O, h (a) = b 0 1 70420 NA OAS 1 Table 3.8: T he resnlts of running rank/ 6 on the algebraic operations from algebra, B 15 , to algebra, M 1 . 68 Subalgebra Homomorphism k Rank( :::;) Time (ms) B16:::; M1 h (0) = h (a)= h (b) = 0 0 1 73950 1 NA OAS 0 1 73990 1 NA OAS 0 1 74220 1 NA OAS 0 1 74450 1 NA OAS 0 1 73880 1 NA OAS h(O) = 0, h(a) =a , h(b) = b 0 0 0 1 0 0 0 1 35640 1 NA OAS 0 1 35370 1 NA OAS 0 1 35480 1 NA OAS h (0) = h (a) = 0, h (b) =a h (0) = h (a) = 0, h (b) = b h(O) = h(b) = 0, h(a) = a h(O) = 0, h(a) = h(b) = a h (0) = h (b) = 0, h (a)= b h(O) = 0, h(a) = b, h(b) =a h (0) = 0, h (a) = h (b) = b Table 3.9: The results of rnnning rank/ 6 on the algebraic operations from algebra, B 16 , to algebra, M 1 . 69 The final point to b e made on the nmtime results of rank/6 comes from simulations done on the algebraic operations of the mono-unary algebra, M 9 (Figure 3-4( c), page 57). The algebra, M 9 , is a three-element mono-unary algebra where f (x) = x, for each x E M 9 . This algebra has seven subalgebras, one of which is the algebra itself. There are twenty-seven homomorphisms from M 9 to itself and the results of running rank/6 on the first fifteen of these are recorded in tables , Table 3.10 and Table 3 .11. When trying to run rank/6 on the remaining algebraic operations of M 9 , Prolog reports the error message, "memory allocation failed" . Fnrthermore, one can see from the tables that the runtimes rapidly increase after the first few homomorphisms have been tested. Recall from the section on complexity analysis in Chapter 2 that the term, 2m"" n+k , in the complexity of rank/6 is a result of the worst-case number of sublists of algebraic operations in the database, for a given algebra. In this particular case, the number of algebraic operations in the database, for M 9 , increases from 1 to 15, when k: = 0 and similarly when k = 1. Thus , for both J..: = 0 and k = 1, the number of sublists is increasing from 2 1 to 2 15 , the worst-rase . A s a r esnlt of this, bot.h the time and space efficiency during these rnns is greatly affected. Fortunately, the results for this algebra are theoretically known already [10]2 , thus the failure to compute results here is not terribly interesting. 2 That is, that mono-unary algebras have rank at most two. 70 Subalgebra Homomorphism k Rank (::;) B g1 ::; M 9 h (0) = h (a) = h (b) = 0 0 1 30 1 1 1560 0 1 30 1 1 1570 0 1 30 1 1 1520 0 1 30 1 1 1560 0 1 40 1 1 1560 h(O) = 0, h(a) =a , h(b) = b 0 0 0 1 0 0 0 1 50 1 1 1580 0 1 100 1 1 1610 0 1 200 1 1 1710 h (0) = h (a) = 0, h (b) =a h (0) = h (a) = 0, h (b) = b h (0) = h (b) = 0, h (a) =a h(O) = 0, h(a) = h(b) =a h (0) = h (b) = 0, h (a)= b h (0) = 0, h (a)= b, h (b)= a h(O ) = 0, h(a) = h(b) = b Time (ms) Table 3.10: The results of running rank/ 6 on the algebraic operations from algebra, B 91 , to algebra, M 9 . 71 Subalgebra Homomorphism k Rank (::;;) B g1 ::;; M 9 h(O) =a, h(a) = h(b) = 0 0 1 450 1 1 1940 0 1 1020 1 1 2550 h(O) =a , h(a) = 0, h(b) = b 0 1 2370 1 1 3900 0 1 5510 1 1 6900 0 1 12680 1 1 14100 0 1 29030 1 1 29890 h (0) = h (b)= a, h (a)= 0 h (0) = h (a)= a, h (b)= 0 h (0) = h (a) = h (b) =a h(O) = h(a) =a, h(b) = b Time (ms) Table 3.11: The results of running rank/ 6 on the algebraic: operations from algebra, B 91 , to algebra, M 9 (continued). The rest of this chapter presents the values of rank obtained from the rank/6 trials done on the above mentioned algebras. Before the results are discussed, the order of the steps which t he user takes to approximate the rank of an algebraic: operation of an algebra are given. Given an algebra, say M, there is a database with filename , algebraM. pl , that initially contains projections. Given that the database has projections on M 1 through M 1, consider subalgebras of M n, where 1 ::;; n ::;; l, and embeddings, B - > uB', where 72 B' :::; Mn+k and n + 1.: :::; l. For each B:::; Mn (n :::; l) , and each homomorphism, h : B ---+ M, chosen by the nser, qnery rank/6 with inpnt arguments , h, n, k, N, and algebraM. pl , returning the approximated rank which binds with the sixth argument. The value of n is dictated by the size of the power of snhalgebra, B. While N , the number of homomorphisms to nse for separation of B', is selected by the user. The value of k is incremented by the code, beginning at 0, up to some maximnm k snch that n + k :::; l. Initially, the number of homomorphisms to use for separation is set at N = 1. ForB, the code then tests every set Y of N homomorphisms from algebraM. pl to determine if they separate B'. It then tests if h lifts to C / Y, where B' :::; C:::; Mn+k, and calculates an approximate rank. For a given N, if some later homomorphism reports a rank less than any preceding homomorphisms, all the preceding homomorphisms with higher rank must be re-done to ensnre that their rank is not any lower. This is because the code selects the homomorphism with the lowest known rank that separates the subalgebra, so there may be a chance that a new homomorphism with lower rank separates the subalgebra being tested. Furthermore, if at any time there is a fail reported in the rnn, one of two things mnst be tried. First, retry the homomorphism after all the others are done. If there is still a fail, increase the valne of N and try again (i.e. it takes more homomorphisms to separate B') , and so on. Continually obtaining fail for N < n + k homomorphisms when B' :::; Mn+k snggests that n + k homomorphisms are always required, which forces an infinite rank. It can be said that the logic as applied to these steps is non-monotonic because initial assumptions may be retracted as new information is acquired. The results 73 for all the rnns done are recorded in tables in Appendix A, at the back of the thesis. Table 3.8 contains the resnlts of rnnning rank/6 on the homomorphisms from algebra, B 15 , a snbalgebra of algebra. M 1 , to M 1 , for k = 0 aucl /,: = 1. The algebra, B 15 , is the two-element snhalgebra of M 1 containing the elements {0, a}. Notice from the table that the third homomorphism defined hy, h (0) = 0 and h (a) = h, has a reported rank of less than or eqnal to one. for /,· = 0. From Example 4, in Chapter 1 (15) , it is known that this homomorphisms has rank less than or equal to two. The disparity between the two results is dne to the restriction on /,: for this particnlar algebra. Becanse k can not exceed zero and N is at least one. k is never greater than or eqnal to N, which is a necessary condition for there to be a fail lifting t o M k+ l \ {c} . The point is that a result for k = 1 cannot be compnted for this algebra and thus a trne comparison of the results cannot be made. The only way to remedy this problem is to m ake the code more efficient. Some thoughts on this are presented in the next ch apter. For the remaining mono-nnary algebras , all the rnns were done with n = 1 and all reported compnted ranks were less than or eqnal to one. This was to be expected for it is known that all mono-nnary algebras are rank at most. t.wo [10], and furthermore, that all mono-unary algebras of size three or less have rank of at most one , which follows from work done in [10]. The next algebra of interest is t he three-element bi-nnary algebra, P 1 , shown in Figure 3-9. That this algebra has an infinite rank is shown implicitly in [11]. 2 The algebra, P 1 , h as one snbalgehra, itself, and (P 1 ) (Fignre 3-10) has nine subalgebras, one 74 of them being itself. The resnlts from rnnning rank/6 on these two snbalgebras, denoted B 11 and B 12 , respectively, are shown in Table 3.12. For B 11 , there is one homomorphism, the projection, from B 11 to P 1 . So, for both k = 0 and 1.: = 1, with n = 1 and N = 1, the reported rank is zero. Ou the other hand , for B 12 there exists fonr algebraic operations of P 1 , the two projections , the minimnm of both coordinates and the maximum of the coordinates . Iu the case of rnnning these four homomorphisms , n = 2, k = 0, are fixed and N = 1 initially. As expected , the two proj ections prodnced rank zero. What is of interest here is that the other two homomorphisms, defined by h (x , y) =min (x, y) and h (x, y) = m ax (.r:, y) prodnced a fail in the qnery when N = 1 and that rank is less than or eqnal to one when N = 2. These resnlts confirm the exp ected results because rank (P 1 ) = oo . \iVhat is happening here is that wheu n = 2, it takes two projections to separate B 12 , tlms wheu N = 1 separation will not happen . Once N is set to two, then the two projections necessary for separation are available and the rank is reported as one. Also , since neither of the two homomorphisms is of rank one when N = 1, there are no other choices for separation but projections. The idea is that as n + k increases, so mnst N, which means the rank is infinite. ba..-- _. - lt ~~ ,..- • •f'l-.._._ ,-, bb /.-, _.... tl ' ..(.Lb I tlI / . _ • Ob tlaa I • , I /f!• au --..........1 / 00 ~ ua Figure 3-10: The algebra, B 12 , a snbalgebra of (P 1 ( 75 Time (ms) Subalgebra Homomorphism k N Rank ( :::;) Bu = P1 h(O)=O , h(a)=a , h(b)=b 0 1 0 0 1 1 0 10 0 1 fail 70 2 1 80 B1 2 = ( P 1) 2 h (:r: , y) =min (.T , y) II (:r. y) = :r: 0 1 0 0 I! (.T. ;tJ) = :tJ 0 1 0 0 11 ( :r . y) = max (.T , y) 0 1 fail 80 2 1 90 Table 3.12: The resnlts of rmming rank/ 6 on the algebraic operations from algebras, Bu and B 12 , to algebra. P 1 . The bi-nnary algebra, P 1 , mentioned above is referred to as a chain algebra because the two fnnctions of the algebra are similar but they work in the opposite direction, seen in Figure 3-9 (page 67). This algebra is the only bi-unary algebra whose rank we know anything abont . The rest of the bi-nnary algebras presented in this chapter are those for which rank/6 fails for at least one homomorphism. Now consider the four-element bi-unary chain. P 12 . of Fignre 3-8 (b) (page 62) and the two snbalgebras, B 121 = P 12 and B 1 22 = (P 12 f The resnl ts of running rank/6 on the homomorphisms from these two snbalgebras to P 12 are presented in Table 3.13. Notice that the algebraic operations from B 121 and B 122 are similar to those of algebra P 1 and the rank results of running these algebrai<' operations are also similar to the results of P 1 (Table 3.12). Specifically, 76 the homomorphisms, h (1:. y) = min (x , y) and h (.T , y) = max (x, y), both fail the rank query when N = 1, and retnrn a rank of one when N = 2. Furthermore, although (PI) 2 has nine subalgehras and (P 12 ) 2 has sixteen suhalgebras, all the snbalgebras take on the same patterns. These similarities between the two algebras suggest t hat the r ank of P 12 is infinite, equal to that. of P 1 . That is, N must b e greater than or equal to n + k in order for there to b e euongh homomorphisms to separate ( P 12 ) n+k · . Time (ms) Subalgebra Homomorphism k N Rank( :::;) B 121 = P 12 /i (:r) = .T 0 1 0 0 1 1 0 10 0 1 fail 15150 2 1 15050 B 122 = ( P 12) 2 h ~ y) =min (.T , y) h (:r. y) = ~ 0 1 0 0 h (:r, y) = y 0 1 0 0 h ~ y) =max (.T, y) 0 1 fail 15070 2 1 15060 -- ~ ~ Table 3.13: The results of running rank/ 6 on the algebraic: operations from algebras, B1 21 and B 122 , to algebra, P 1 2. 77 Subalgebra Homomorphism k N Rank B41 = P 4 h(O) = 0, h(1) = 1 0 1 0 0 1 1 0 0 2 1 0 0 0 1 fail 10 2 1 10 1 fail 10 2 1 620 0 1 0 0 1 1 0 10 0 1 0 0 1 1 0 0 0 1 fail 20 2 1 10 1 fail 10 2 1 660 B 42 = (P tt) 2 h (:r. y) =min (.x, y) 1 h (.-r . y) = :r: h (.?:.y) =y h (.1:. y) =max (x , y) 1 ~ Time (ms) Table 3.14: The results of rnnning rank/ 6 on the algebraic. operations from algebras, B 41 and B 42 , to algebra, P 4 . To get a look at the behavior of the previous two chain algebras when n + k = 3, it is wise to look at the two-element chain algebra, P 4 (Fignre 3-3 , page 56) , for which the computational model has t he capability of reaching ·h , + k: = 3. Again, P 4 has similar 78 subalgebras and homomorphisms as both P 1 and P 12 , as well as the same rank results for n + k = 1 a11d 2 (Table 3.14). Together these facts lead to the belief that P 4 also has an infinite rank. In the case of P 4 , it is possible to look at the algebraic operations corresponding to (P 4 ):3 . The algebra (P 4 ) 3 has sixty-fonr homomorphism from it to P 4 , each of which fails a rank query when N = 1 or 2, and returns a rank of one when The last two algebras to he presented are the three-element bi-unary algebras, P 10 and P 11 (Figme 3-7. page 60), which are very dose i11 stmdme to algebra P 1 . The algebra, P 11 , has two snbalgebras, the algebra itself, denoted B 111 , and the one-element 2 algebra with nni\'erse {0}, denoted B 112 . Fmthermore, the algebra (P u) has thirteen 2 snbalgebras with (P 11 ) de11oted by B 113 . The resnlts of running rank/6 with these three snbalgebras a11d the corresponding algebraic operations appear in Table 3.15. For this 2 algebra, there is one more algebraic operation from (P u) to P 11 , than there was from 2 (P 1 ) to P 1 , and it also fails the rank qnery when N = 1. Again, this leads to the belief that this algebra ha.'3 infinite rank as well , bnt it is possible that this one extra homomorphism translates to an algebraic operation with a finite rank for larger k. 3 The results of running (P ~ are not presented in table format because of the large number of homomorphisms. 79 Subalgebra Homomorphism k N Rank ( s;) Bu1 = P u h (:1:) = 0 0 1 1 0 1 1 1 150 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 fail 80 2 1 90 1 fail 70 2 1 80 " (:r ) = .7: Bu 2 s; P n B u 3 = (Pn ) " (0) = 0 2 II (.r. y) = 0 II (.r. y) =min (:r:, y) -. ;:;.•"' 0 Time (ms) h (:r. y) = :J: 0 1 0 10 h (:1:. y ) = y 0 1 0 0 h (:t:. y) = max (.r , y) 0 1 fail 70 2 1 90 ~ Table 3.15: The resul ts of nmning rank/ 6 on the algebraic operations from algebras , Bu1 , Bu2 and B in · to algebra; P u. The results for algebra. P 10 ; are seemingly similar to the rest but are less conclusive since fewer nms were clone aud there is no prior theoretical knowledge of its rank. This algebra h as three snbalgebms ; B 101 , B 102 , and B 103 , which generate a total of five algebraic operations. two from B 101 , one from B 102, and two from B 103 , to P 10 . The results 80 of running rank/6 for these operations are given in Table 3.16. As usual, the ranks of the algebraic operations when n = 1 are either zero or one. The power algebra, (P 10 ) 2 , has eighteen homomorphisms which map elements from it to P 10 , all of which, aside from the two projections, failed the rank query when N = 1. Again as we have no a priori knowledge, these results are far less suggestive of infinite rank. Like all the rest, however, it suggests that this algebra may be worth looking at theoretically to see if it has an infinite rank. Subalgebra Homomorphism k Rank( :::;) B 101 = P w h (:r:) = 0 0 1 0 1 1 250 0 0 0 1 0 0 0 0 0 1 0 0 0 1 10 1 1 450 0 0 0 1 0 0 h (x) = x B 102 :::; P w B103 :::; P w h (0) = 0 h (x) = 0 h (x) = x Time (ms) Table 3.16: The results of running rank/6 on the algebraic operations from algebras, Bw1 , B102 and B w3, to algebra, Pw . 81 The results of the nms done on the remaining bi-unary algebras can be found in Appendix A along with the rest of the rank simulation results. For all the algebras, aside from the bi-unary algebras mentioned above, n = 1 is the only case looked at. Further study for higher values of n and h: on all the algebras presented, may produce different results. 3.3 Summary The results of running both of the predicates, make_projections/4 and rank/6 , are found in this chapter or Appendix A. The actual runtimes of make_projections/4 are compared to the results of the complexity analysis , given in detail in Chapter 2. A discussion of simulations done using rank/6 is presented on both the runtimes of the simulations and the rank approximations obtained. The focus of this discussion is centered around the six more interesting algebras , M 1 , P 1 , P 4 , P 10 , P 11 , and P 12 , of the twenty-four studied. It is shown that the computational model provides simulated results consistent with known theoretical results of rank. Overall, the system is shown to work on the algebras introduced and the process of approximating rank with the computational model is put to practice. It is important to emphasize, that in approximating rank, we are approximating au upper bound. 82 Chapter 4 Conclusion 4 .0 Introduction The r.ondusions of the thesis are presented in the first section of Chapter 4. The second section of this chapter presents various ideas on possible future research in the area of the thesis. 4.1 Conclusion The research of this thesis presents a computational model for the purpose of finding a practical connection between the fields of Mathematics and Computer Science through the application of Nat ural Language Processing and Logic Programming techniques to the study of algebras . Through the process of exploring this connection, the author has created a r.ompntational model in the programming language Prolog, which can be 83 used to approximate the rank of nnary algebras and their algebraic operations. The computational model was strnc.tured after the ideas of Natural Language Processing, by viewing universal algebra as a language. By creating this model and obtaining feasible results , the major goal of the research has been met. The results of the research indnde tools for working with finit e unary algebras. The centerpiece of these tools is the predicate which is nsed to approximate the rank of algebras and their algebraic operations. Althongh definitive answers can not be caknlated nsing the predicate for rank. mnch can be learned in its finite approximations. The rank predicate is nsecl for three purposes. The first purpose is to confirm computationally, what has been proven theoretically. The second purpose is to spot trends or tendencies in the K th approximation ranks of algebras. The third purpose of the rank predicate is to find algebra.c:; that show potentially interesting attribntes for further theoretical work, thereby avoiding frnitless work on nninteresting algebras. The rest of the tools created to facilitate the implementation of the rank predicate are nsefnl in their own right. These tools indnde Prolog predicates which generate snbalgebras, homomorphism.s and fador algebras on finite nnary algebras. One Prolog predicate partitions an integer into a finit e list and another bnilds a finite power algebra of a unary algebra. Each of these tools as well as a few others can be nsed outside the scope of the rank predicate for which they were written. The biggest obstacle to the research done in this thesis is the computing limitations of the computational model. As is stated in Chapter 3, the approximation of rank is 84 bounded to small values of k in most instances. Other than the work done on the trivial unary algebras , the highest value of k reached while approximating the rank of an algebraic operation is four. It was shown that this limit is due to the time and space used while generating all the possible subalgebras of an algebra. Generating these subalgebras is a necessary step in the computational model. Each rank approximation computation continues until the finite time and space limitations are encountered. The author has come up with some possible remedies for this problem which will be discussed in the next section on p ossible future work which may be done on the research in question. 4.2 Future Work This section is a discussion of possible future work to be done on the computational model. First, a presentation of some ideas which may help to cut the time and space costs incurred while rnnning the current model. This is followed with suggestion for expanding t he current work. In each case, the discussion is limited to a brief overview of the idea in mind. One of the more obvious ideas is to assert subalgebras as atoms once they are found. As the code stands, a subalgebra may be generated repeatedly throughout the course of a run. Even though generating all the subalgebras of an algebra once can be quite expensive, and this would not change, it would make sense to not generate them again. In conjunction with this idea, another idea would be to save the subalgebras of an algebra as a lattice structure. In some cases, a goal of the computational model is to 85 find all the subalgebras that lie between two specific. subalgebras. By viewing all the subalgebras of au algebra as a lattice, finding all the required subalgebras between two subalgebras becomes a matter of finding the endpoints of some subinterval in the lattice. The subinterval can theu be traversed as needed. Another idea ';vhic.h is worth exploring comes from Ceri , Gottlob , and Tanc.a's, Logic Programming and Datal)(],ses. [4], in which they discuss the use of relational databases in c.onjunctiou with Prolog. The idea is to create an interface between Prolog and an external relational database for dealing with large data sets. Upon further research, it has been found that the SICStus version of Prolog, which is used for this thesis, has a built in interface which does exactly this. Once again, the biggest problem of this thesis is the generation and storage of potentially large quantities of subalgebras. Also, the databases of homomorphisms of known rank is constantly growing. It is these two things which account for most of the space consumption while running the rank predicate. Outside trying to improve the efficiency of the current code, the ground work has been laid for expansion into other types of algebras and tools of algebras. The ultimate goal would be to create a Prolog system which could he used as an algebra calculator. As a final note, UNBC is iu the process of receiving a new super computer that may increase the capacity of the rode as it stands. 86 4.3 Summary The research of this thesis provides an original and nmqne computational model for the purposes of approximating rank. The model conlcl prove a valnable tool for both algebraists and topologists when nsed for duality theory. Furthermore, t he computational model created in the research contains many secondary tools that can be used by algebraists. 87 Bibliography [1] Francesco Bergadano and Daniele Gunetti , Inductive Logic Programming: From Machine Learning to Software Engineering, The MIT Press, Cambridge, Mass., 1996. [2] Ivan Bratko, Prolog Pr-ogramming for Artificial Intelligence, Second Edition, Addison- \i\Tesley Publishing Company, Reading, Mass., 1990. [3] Stanley Burris and H.P. Sankappanavar, A Cours e in Universal Algebra, SpringerVerlag New York Inc. , New York, NY, 1981. [4] S. Ceri, G. Gottlob , aud L. Tanca, Logic Programming and Databases, SpringerVerlag, New York, NY. 1990. [5] S. Ceri, D. fvlandrioli , and L. Sbattella, Th e Art and Craft of Computing, AddisonWesley Lougmau Ltd .. Edinburgh, Scotland, 1998. [6] David :rvl. Clark. Pawel M. Idziak, Lonsindi Sabourin, Csaba Szabo, and Ross Willard, Natural Dualities For Quasivarieties Generated By A Finite Commutative Ring, Preprint, 2000. [7] W.F. Clocksin and C.S. Mellish, Pr-ogramming in Prolog, Fourth Edition, SpringerVerlag, New York , NY. 1994. [8] Michael A. Covington. Natural Language Processing for PROLOG Programmers, Prentice-Hall , Inc., Englewood Cliffs, N J , 1994. 88 [9] Joseph A. Gallian, Contemporary Abstract Algebra. Third Edition, D.C. Heath and Company, Lexington, rdA, 1994. [10] Jennifer Hyndman , Mono-unary Algebras are Stmngly Dualizable, Journal of the Australian Tviathematical Society, Series A, accepted , 1999. [11] Jennifer Hyndman and Ross \iVillard, An Algebra That Is Dualizable But Not Fully Dualizable. Journal of Pnre aud Applied Algebra, accepted, 1999. [12] The Intelligeut Systems Laboratory, SICStus Prolog Us er 's Manual, Swedish Institute of Computer Scieuce, Kista, Sweden, 1995. [13] George F . Lnger and \iVilliam A. Stubblefield, Ar·tificial Intelligence and the Design of Exper·t Systerns, The Benjamin/ Cummings Puhlishiug Company, Inc., Redwood City, CA, 1989. [14] David Iviaier and David S. \iVarren, Computing with Logic: Logic Programming with Prolog, The Benjamiu/ Cummings Publishing Company, Inc., Menlo Park, CA, 1988. [15] Anil Nerode and Richard A. Stone, Logic for Applications, Springer-Verlag, New York, NY , 1993. [16] Richard A. O 'Keefe, Th e Cmft of Prolog, The MIT Press, Cambridge, MA, 1990. [17] Peter Ross, Advanced Pmlog: Techniques and E.r,amples, Addison-Wesley Publishing Company, Readiug. rviass .. 1989. [18] Uwe Schoning, Logic for Computer Science, Birkhauser , Boston, MA,1989. [19] Jeffrey D. Smith, Des·ign and Analysis of Algorithms, PWS-Kent Publishing Company, Bostou, T\IA , 1989. [20] Leon Sterling and Elmd Shapiro, Th e Art of Pmlog: Advanced Programming Techniques, Second Edition, The MIT Press, Cambridge, MA , 1994. 89 [21] Mark Allen Weiss, Data Structures and AlgoTithm Analysis in C++, The Benjamin/ Cmnmings Pnblishing Company, Inc. , Redwood City, CA, 1994. [22] Ross Willard, N ew Tools joT Pro ving Dualizability, Preprint , 1998. 90 Appendix A Appendix: Tables Appendix A contains the tables of results obtained from running rank/6 on some mono-unary and hi-unary algebras. The tables indude the subalgebra names , the homomorphisms , the size of f..:. the approximated rank , and the runtimes in milliseconds. Some tables include a listing of the value of N , for those without this listing N = 1. 91 Time (ms) Subalgebra Homomorphism k Rank (::;) B 11 = M 1 h(O) = h (a) = h(b) = h(c) = 0 0 1 35700 1 NA OAS 0 1 35460 1 NA OAS 0 1 35760 1 NA OAS 0 1 35530 1 NA OAS 0 1 35510 1 NA OAS h (0) = h (n) = 0, h(b) =a, h(c) = h 0 1 35470 1 NA OAS 0 1 35790 1 NA OAS 0 1 35710 1 NA OAS 0 1 35850 1 NA OAS h(O) = h(a) = h(b) = 0, h(c) =a h (0) = h (o) = h (b) = 0, h(c) = b h(O) = h (h) = h(c) = 0, h(b) =a h (0) = h (a) = 0, h (b)= h (c) = a h (0) = h (a) = h (c)= 0, h (b)= b h(O)=h (a) =O , h(b)=b, h(c)=a h(O) = h(a ) = 0, h(b) = h(c) = b 92 Subalgebra Homomorphism k k Bu = M1 h (0) = h (h) = 0, h (a ) =a , h (c)= c 0 1 36380 1 NA OAS h(O) = 0, h(a) = h(b) =a , h(c) = c 0 1 37060 1 NA OAS 0 0 0 1 0 0 0 0 0 1 0 0 0 1 108 100 1 NA OAS 0 1 108250 1 NA OAS 0 0 0 1 0 0 h (.7:) = :r B 12 ~ M 1, 11 (0) =0 B12 = {0} B 13 ~ M 1, h (O ) = h (h ) = 0 B13 = {O, b} h (0) = 0. h (b) =a h (0) = 0. h (b) = b 93 ~ Time (ms) Time (ms) Subalgebra Homomorphism k Rank ( :::; ) B14 :::; M 1, h (O) = h (a) = h (c) = 0 0 1 73870 1 NA OAS 0 1 73660 1 NA OAS 0 1 73840 1 NA OAS 11 (0) = 0, h (a) = a, h (c) = c 0 0 0 1 0 0 0 1 142680 1 NA OAS 0 0 0 1 0 0 0 1 70420 1 NA OAS B14 = {0 , a, c} 11 (0) = h(a ) = 0, h(c) =a h (0) = h (a) = 0, h (c)= b B1s :::; M1 , 11 (0) = h (a) = 0 B1s = {0 , a} h (O) = O, h(a) =a h (O) = O, h(a) = h -·:;.•"" :- 94 Subalgebra Homomorphism k Rank (::;) Time (ms) B16 ::; M1 , h(O) = h(a) = h(b) = 0 0 1 73950 1 NA OAS 0 1 73990 1 NA OAS 0 1 74220 1 NA OAS 0 1 74450 1 NA OAS 0 1 73880 1 NA OAS h (0) = 0, h (a) .= a, h (b) = b 0 0 0 1 0 0 0 1 35640 1 NA OAS 0 1 35370 1 NA OAS 0 1 35480 1 NA OAS B16 = {O , o..h} h(O ) = h(a) = 0, h(b) =a h (0) = h (a) = 0, h (b)= b h (0) = h (b) = 0, h (a) =a h(O) = 0, h(a) = h(b) =a h (0) = h (b)= 0, h (a)= b h(O) = 0, h(a) = b, h(b) =a h(O ) = 0, h (a) = h(b) = b 95 Time (ms) Subalgebra Homomorphism k Rank( :::;) B :n = M 1 h (O) = h(1) = 0 0 1 470 1 1 2310 2 1 31960 0 0 10 1 0 0 2 0 0 0 0 0 1 0 0 2 0 0 h (O) = 0, h (1) = 1 B 32:::; M ~ II (0) = 0 B32 = {0} 96 Time (ms) Subalgebra Homomorphism k Rank( :::;) B 41 = M 4 h(O) = h(1) = 0 0 1 850 1 1 4150 2 1 58360 0 0 0 1 0 0 2 0 0 0 1 860 1 1 4160 2 1 58160 0 1 860 1 1 4190 2 1 58680 " (0) = 0, h (1) = 1 " (0) = 1, h (1) = 0 h (O) = h(1) = 1 97 Subalgebra Homomorphism k Rank (:S::) B 42 :S:: M 4, h (1) = 0 0 1 1700 1 1 8330 2 1 116990 0 0 0 1 0 0 2 0 0 0 0 0 1 0 0 2 0 0 0 1 1680 1 1 8400 2 1 117300 E 42 ={1} 11 (1) =1 B 4:1 :S:: M 4. B 43 = " (0) = 0 {0} h (0) = 1 98 Time (ms) Subalgebra Homomorphism k Rank( :::;;) B 51 = M 5 h (0) = 0, h (1) = 1 0 0 0 1 0 0 2 0 0 3 0 10 0 1 50 1 1 100 2 1 380 3 1 35650 ,, (0) = 1, h (1) = 0 99 Time (ms) Subalgebra B 51 =M5 Time (ms) Homomorphism k Rank h(O) = h(a) = h(b) = 0 0 1 30 1 1 1040 0 1 20 1 1 1060 0 1 20 1 1 1040 0 1 20 1 1 1040 0 1 30 1 1 1050 h (0) = 0, h (a) = a, h (b) = b 0 0 0 1 0 0 0 1 40 1 1 1080 0 1 80 1 1 1110 0 1 190 1 1 1220 h (0) = h (a) = 0, h (b) =a h (0) = h (a) = 0, h (b) = h h (0) = h (b) = 0, h (a) =a h (0) = 0, h (a) = h (b) =a h (0) = h (b) = 0, h (a) = b h (O) = 0, h(a) = b, h(b) =a h (0) = 0, h (a) = h (b) = b 100 ~ Subalgebra Homomorphism k Rank( ::::;) B 62::::; M G, h (0) = h (b) = 0 0 1 430 1 1 2560 0 1 430 1 1 2590 0 0 0 1 0 10 0 0 0 1 0 0 0 1 430 1 1 2510 0 0 0 1 0 0 0 1 430 1 1 2530 B 62 = {0, b} h (0) = 0, h (b) =a " (0) = 0, h (b) = b ~ ::::; M (i . B 53 = {0} B 64::::; M 5, B 64 ,, (0) = 0 h(O) = h(a) = 0 = {0, a} h (0) = 0, h (a) =a h (0) = 0, h (a) = b 101 Time (ms) Subalgebra Homomorphism k Rank (:S) Bn = M 1 h (0) = h (a) = h (b) = 0 0 1 0 1 1 250 0 1 10 1 1 280 11 (0) = 0, h (n) = a, h (b) = b 0 0 0 1 0 0 0 0 0 1 0 0 0 1 10 1 1 520 0 0 0 1 0 0 h (0) = h (a) = 0, h (b) =a B 12 :S M;. h (0) = 0 B12 = {0} B 73 :S M1 , h(O) = h(a) = 0 B7.3 = {0. a} h (0) = 0 , h (a) =a 102 Time (ms) Time (ms) Subalgebra Homomorphism k Rank( :::;) Bs1 = M s h (0) = h (a) = h (b) = 0 0 1 30 1 1 500 0 1 10 1 1 500 0 1 10 1 1 500 h (0) = 0, h (a) = a, h (b) = b 0 0 0 1 0 0 0 1 10 1 1 510 0 1 20 1 1 520 0 1 50 1 1 1140 0 0 0 1 0 0 h (0) = h (a) = 0, h (b) = b h (0) = h (h) = 0, h (a) = a h (O) = h(a) = b, h(b) = 0 h (0) = h (a) = h (b) = b Bs2:::; M s, h (h) = 0 Bs2 = {b} h (b) = h 103 Subalgebra Homomorphism k Rank( :::;) B s3:::; M s, " (0) = h (b) = 0 0 1 40 1 1 1010 0 0 0 1 0 0 0 1 50 1 1 1070 0 1 50 1 1 1050 0 0 0 1 0 0 0 1 60 1 1 2130 0 1 40 1 1 960 0 0 0 1 0 0 0 1 40 1 1 980 ~ = {0, h} " (0) = 0, h (b) = b " (0) = {J : h (h) = 0 " (0) = h (b) = b B s4:::; M R, " (0) = 0 BR4 = {0} " (0) = h B 8.s:::; M g. I! (0) = h (a) = 0 B 8 ;, = {0 . a} h (0) = 0, h (a) = a h (O) = h (a) = b 104 Time (ms) Subalgebra Homomorphism k Rank (:S) B g1 :S M g h (0) = h (a) = h (b) = 0 0 1 30 1 1 1560 0 1 30 1 1 1570 0 1 30 1 1 1520 0 1 30 1 1 1560 0 1 40 1 1 1560 h (0) = 0, h (a) =a , h (b) = b 0 0 0 1 0 0 0 1 50 1 1 1580 0 1 100 1 1 1610 0 1 200 1 1 1710 h (0) = h (a) = 0, h (b) = a h (0) = h (a) = 0, h (b)= b 11 (0) = h (b) = 0, h (a) = a h (0) = 0 , h (a) = h (b) =a h (0) = h (b) = 0, h (a) = b ~ h (0) = 0, h (a)= h, h (b) =a 11 (0) = 0. h (a)= h (b) = b 105 Time (ms) Time (ms) Subalgebra Homomorphism k Rank ( :::;) B g1 :::; M g h (0) =a , h (a) = h (b) = 0 0 1 450 1 1 1940 0 1 1020 1 1 2550 h (0) = o., h (o) = 0, h (b) = h 0 1 2370 1 1 3900 0 1 5510 1 1 6900 0 1 12680 1 1 14100 0 1 29030 1 1 29890 h (0) = h (b) =a , h (a)= 0 h (O) = h(a) =a , h(b) = 0 h (0) = h (a) = h (h) =a h (O) = h (u.) =a , h(b) = b 106 Subalgebra Homomorphism k Rank B 101 = M 10 h (0) = h (a)= h (b) = 0 0 1 0 1 1 80 h (O) = 0, h (a) =a, h(b) = b 0 0 0 1 0 0 0 1 10 1 1 110 0 1 10 1 1 140 0 0 0 1 0 0 0 1 10 1 1 150 0 0 0 1 0 0 h (O) = 0. h(a) = b, h(b) =a B 102 ~ M 10 , h (a) = h (b) = 0 B102 = {a.b} h (a) = a, h (b) = h h (a) = h, h (b) =a. B 103 ~ M 10 , B103 h (0) = 0 = {0} 107 ~ Time (ms) Time (ms) Subalgebra Homomorphism k Rank Bu1 = M n h(O) = 0, h(a) = h(b) =a 0 1 0 1 1 200 II (0) = 0, h(a) =a , h(b) = b 0 0 0 1 0 0 0 1 10 1 1 220 0 0 0 1 0 0 0 1 10 1 1 400 h (0) =a, h (a) = h (b) = 0 Bu2 ~ Mn , h (O) = 0, h(a) =a Bw2 ={ a.b} h (0) =a , h (a) = 0 108 ~ Subalgebra Homomorphism Rank (::;) B121 = M1 2 h(O) = 0, h(a) =a, h(b) = b 0 0 0 1 0 0 2 0 0 0 1 llO 1 1 380 2 1 72045720 0 1 llO 1 1 370 2 1 72013680 k h (0) =a, h(a) = h, h(b) = 0 h(O) = h, h(a) = 0, h(b) =a Time (ms) Subalgebra Homomorphism k N Rank (::;) Bu = P1 h (0) = 0. h (a) = a, h (b)= b 0 1 0 0 1 1 0 10 0 1 fail 70 2 1 80 B12 = (P I) 2 h (;c , y) =min (x , y) Time (ms) h (x, y) = x 0 1 0 0 h (x , y) = y 0 1 0 0 h (.r:. y) =max (:r, y) 0 1 fail 80 2 1 90 109 Time (ms) Subalgebra Homomorphism k Rank (:S) B 31 = P 1 h (O) = h (1) = 0 0 1 20 1 1 60 2 1 120 0 0 0 1 0 0 2 0 10 0 0 0 1 0 0 2 0 0 " (0) = 0, h (1) = 1 B 12 :S P :l · B 32 " (0) = 0 = {0} 110 Time (ms) Subalgebra Homomorphism k N Rank (::;) B 41 = P 4 h (0) = 0 , h (1) = 1 0 1 0 0 1 1 0 0 2 1 0 0 0 1 fail 10 2 1 10 1 fail 10 2 1 620 0 1 0 0 1 1 0 10 0 1 0 0 1 1 0 0 0 1 fail 20 2 1 10 1 fail 10 2 1 660 B42 = (P 4) 2 h (:r:, y) =min (.r., y) 1 h (.?:, y) = X h (:r:, y) = y h (.r. , y) =max (.1: , y) 1 111 Subalgebra Homomorphism k Rank( :::; ) B 51 = P 5 h (O) = h(1) = 0 0 1 30 1 1 60 2 1 1240 0 0 0 1 0 0 2 0 0 0 0 0 1 0 0 2 0 0 ,, (0) = 0, h (1) = 1 B 52:::; P 5. " (0) = 0 B52 = {0} Time (ms) Subalgebra Homomorphism k Rank( :::;) B 61 = P6 h(O) = 0, h(1) = 1 0 0 0 1 0 0 2 0 0 3 0 0 112 Time (ms) Subalgebra Homomorphism k Rank ( ::::;) B71 = P1 h(O) = h(1) = 0 0 1 30 1 1 90 2 1 1740 0 0 0 1 0 0 2 0 10 0 1 40 1 1 100 2 1 1760 0 1 30 1 1 80 2 1 1780 h (0) = 0, h (1) = 1 h (0) = 1, h (1) = 0 h (0) = h (1) = 1 113 Time (ms) Subalgebra Homomorphism k Rank( :::; ) B 12:::; Pr. h (1) = 0 0 1 40 1 1 170 2 1 3460 0 0 0 1 0 0 2 0 0 0 0 0 1 0 0 2 0 0 0 1 50 1 1 170 2 1 3440 B 72 ={1} 11 (1) =1 Br:{ :::; P 1 . " (0) = 0 Br?. = {0} h (0) = 1 114 Time (ms) Subalgebra Homomorphism k Rank (::S) B 81 = P 8 h (0) = 0, h (1) = 1 0 0 0 1 0 0 2 0 0 3 0 0 0 1 70 1 1 150 2 1 540 3 1 63210 " (0) = 1, h (1) = 0 Time (ms) Subalgebra Homomorphism k Rank ( :::;) B 91 = P 0 h (0) = 0, h (1) = 1 0 0 0 1 0 0 2 0 0 3 0 0 0 1 80 1 1 140 2 1 520 3 1 61060 " (0) = 1, h (1) = 0 115 Time (ms) Time (ms) Subalgebra Homomorphism k Rank B IOI= p lO h (x) = 0 0 1 0 1 1 250 0 0 0 1 0 0 0 0 0 1 0 0 0 1 10 1 1 450 0 0 0 1 0 0 BIOI= {O , a,b} h(.r) =.T B 102 ~ P w, h (0) = 0 B102 = {0} B 103 ~ P w, h (x) =O B103 = {0, a} h (.r)= .T 116 ~ Time (ms) Subalgebra Homomorphism k N Rank (::::;) Bn1 = P ll h (x) = 0 0 1 1 0 1 1 1 150 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 fail 80 2 1 90 1 fail 70 2 1 80 !J.(:r) =.T h (0) = 0 Bn2 ::::; P n B113 = (P1 1) 2 h (:1:. y) = 0 h (:r. y) =min (.T, y) 0 h (.1:. y) = .T 0 1 0 10 h. (:7:. y) = y 0 1 0 0 h (.1:. y) =max (x, y) 0 1 fail 70 2 1 90 117 Subalgebra Homomorphism k N Rank( -:::;) B 121 = P 12 h (:r:) = X 0 1 0 0 1 1 0 10 0 1 fail 15150 2 1 15050 B 122 = ( P 12) 2 h (:1:, y) =min (.1: , y) Time (ms) h(:r.y) = :1: 0 1 0 0 h(:l:.y) = y 0 1 0 0 h (:1:, y) =max (x , y) 0 1 fail 15070 2 1 15060 118 Appendix B Appendix: Code The appendix contains the predicates written and implemented for the purpose of approximating the rank of homomorphisms of finit e unary algebras . All code is written using SICStus Prolog. The appendix has been broken into the files that the code is contained in. Each file includes a header containing the name of the file, a brief description of the file , the author's name. creation and modification dates, the names of the predicates in the file , and the names of the calling predicates ·where applicable. Each predicate begins with detailed documentation. Following the convention of the SICStus Prolog manual [12], when introducing predicates, the arguments of the predicates have one of the following forms: : ArgName - This argument should be instantiated to a term denoting a goal or a clause or a predicate name, or which otherwise needs special handling of module prefixes. +ArgName - This argument should be instantiated to a non-variable term. 119 -ArgName - This ar.e;ument should be uninstantiated. ? ArgName - This argument may or mat not b e instantiated. All code was written and implemented by the author of this thesis , Richard K. Little, during the years of 1998 aud 1999. 120 / ************ **************************************** **************** / I* I * FILE: rank.pl Approximates the rank of an algebraic operation I* of a fixed finite unary algebra. I* I* Rich Little I * BY: 16 Dec 1998 I * CREATED: I* MODIFIED: 23 Jan 1999 (changed variables) 01 Feb 1999 (added for_each_part 1 9) I* 03 Mar 1999 (moved the call to get_Ysl5) I* I* I * PREDICATES : rank l6 I* rank l 9 I* for_each_kl9 I* for_each_part l 9 I* for_each_D I 8 I* for each_CI7 I* there_exists_YI7 I* for_each_g l 3 I* I * CALLED-BY: I* *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I ! ********************************************************************! % rank(+HOMO,+ SMALLN,+K,+N,+FILE,-RANK) % The argument, HOMO, is instantiated with a c lause form, % homomorphism l5 , an algebraic operation of a given algebra. The % rank of the algebraic operation is approximated for values up % to some K, and binds with argument, RANK . The argument, FILE, % is the filename of a file containing the database of algebraic % operations with known rank. rank(homomorphism(R,K,algebra(B,FB) ,algebra(M,FM), [DH,H]) ,Sn,K,N,F,R) list_to_ord_set(B,OB), ord_functi ons( FB,OFB ), list_to_ord_set(M,OM ), ord_functi ons(FM, OFM ) , list_t o_ord_set(DH,ODH), list_to_ord_set(H ,OH), is_algebra(algebra( OB,O FB) ), is_algebra (a lgebra(OM,OFM)), is_homomorphi s m (homomo rphism(R,K,algebra(OB, OFB) ,algebra(OM,OFM), [ODH,OH])), make_M_to_the_n(algebra(OM,OFM) ,Sn,algebra(Mn,FMn)), is_algebra(algebra(Mn,FMn)), list_to_ord_set(Mn, OMn) , ord_functions(FMn,OFMn), subalgebra(algebra( OB,O FB) ,algebra(OMn,OFMn)), !, rank([ ODH , OH] ,algebra(OB,OFB) ,algebra(OM, OFM) ,Sn,K,N,F,-2,R) % rank(+HOMO,+ALG_B,+ALG_M,+SMALLN,+K,+N,+FILE,+MAXRANK,-RANK) % The argument, HOMO, represents a homomorphism from an algebra, 121 ALG_B, to an algebra, ALG_M, for some positive integer K. If the rank of HOMO already exists in the database, FILE, return the rank, RANK. Else, the rank is approximated and the argument RANK binds with the maximum rank, MAXRANK, plus one. In this case the database of homomorphisms is consulted as facts. Sometimes it is more prudent to leave the database as a file and read the terms in one at a time. The lines of clause one that our commented are used for this purpose. % % % % % % % % rank(Homo,Alg_B,Alg_M,Sn,K,N,F,MR,R) % open(F,read,Stream), % read(Stream,Term), % check_dBase(Term,Stream,K,Homo,Alg_B,Alg_M,R), % close (Stream) , ! . homomorphism(R,K,Alg_B,Alg_M,Homo), ! . rank(Homo,Alg_B,Alg_M,Sn,K,N,F,MR,R) ! , for_e ach_k(O,Homo,Alg_B,Alg_M,Sn,K,N,F,MR,TR), R is TR + 1, open(F,append,Stream), write(Stream,homomorphism(R,K,Alg_B,Alg_M,Homo)), format (Stream, "-w", ['. ')) , format (Stream," -n", [)), format (Stream, "-n", [)), close (Stream) , assert((homomorphism(R,K,Alg_B,Alg_M,Homo))), % for_each_k(+I,+HOMO,+ALG_B,+ALG_M,+SMALLN,+K,+N,+MAXRANK,-RANK) % For all 0 <= I < = K, where I and K are integers, partition % I into a list of size SMALLN to be used to approximate the % rank, RANK, of a homomorphism, HOMO. If I is strictly % greater than K, RANK binds with MAXRANK. for_each_k(I,Homo,Alg_B,Alg_M,Sn,K,N,MR,R) I = < K, SnPlusK is Sn + I, make_M_to_the_n(Alg_M,SnPlusK,algebra(MnK,FMnK)), list_to_ord_set(MnK,OMnK), ord_functions(FMnK,OFMnK), is_algebra(algebra(OMnK,OFMnK)), partition_k(I,Sn,PList), ! , for_each_part(PList,Homo,Alg_B,Alg_M,algebra(OMnK,OFMnK) , K,N,MR, TR), I1 is I + 1, for_each_k (I1,Homo,Alg_B ,Alg_M ,Sn,K,N,TR, R) for_each_k(I,Homo,Alg_B,Alg_M,Sn,K,N,R,R). % for_each_part(+PARTS,+HOMO,+ALG_B,+ALG_M,+ALG_MnK,+K,+N,+MAXR,-R) % If all partitions in the list argument, PARTS, are exhausted, % then argument, R, binds with MAXR, the maximum rank of % homomorphism, HOMO. Otherwise, recursively traverse list, PARTS, to approximate the rank of homomorphism, HOMO. % for_each_par t([) ,Homo,Alg_B,Alg_M,Alg_MnK,K,N,R,R). 122 for_each_part( [ Part!Parts] ,Homo,Alg_B,Alg_M,Alg_MnK,K,N,MR,R) embed_B(Alg_B,Part,algebra(Bprm,FBprm)), list_to_ord_set(Bprm,OBprm), ord_functions(FBprm,OFBprm), is_algebra(algebra(OBprm,OFBprm)), subalgebra(algebra(OBprm,OFBprm) ,Alg_MnK), make_hprime(Homo,algebra(OBprm,OFBprm) ,Hprm), is_homomorphism(homomorphism(R,K,algebra(OBprm,OFBprm) ,Alg_M,Hprm)), bagof(Alg_D,subalgebra(algebra(OBprm,OFBprm) ,Alg_D,Alg_MnK) ,SubAlgs_D), ! , for_each_D(SubAlgs_D,Hprm,Alg_M,algebra(OBprm,OFBprm) ,K,N,MR,TR), for_each_part(Parts,Homo,Alg_B,Alg_M,Alg_MnK,K,N,TR,R). % for_each_D(+ALGS_D,+HPRIME,+ALG_M,+ALG_BPRIME,+K,+N,+MAXRANK,-RANK) % If all the subalgebras in the list, ALGS_D, are successfully % exhausted, RANK binds with argument, MAXRANK. Otherwise, % recursively traverse the list, ALGS_D, looking for only those % algebras in the list which the homomorphism, HPRIME, lift to. % Finally, if HPRIME does not lift to an algebra in the list, % ALGS_D, move on to the next algebra. for_each_D([] ,Hprm,Alg_M,Alg_Bprm,K,N,R,R). for_each_D([algebra(D,FD) IAlg_Ds] ,Hprm,Alg_M,Alg_Bprm,K,N,MR,R) list_to_ord_set(D,OD), ord_functions(FD,OFD), lifts(Hprm,algebra(OD,OFD) ,Alg_M), get_Ys(Alg_M,algebra(OD,OFD) ,K,N,Ys), bagof(Alg_C,subalgebra(Alg_Bprm,Alg_C,algebra(OD,OFD)) ,SubAlgs_C), ! , for_each_C(SubAlgs_C,Hprm,Alg_M,Alg_Bprm,Ys,MR,TR), for_each_D(Alg_Ds,Hprm,Alg_M,Alg_Bprm,K,N,TR,R). for_each_D([Alg_D!Alg_Ds] ,Hprm,Alg_M,Alg_Bprm,K,N,MR,R) for_each_D(Alg_Ds,Hprm,Alg_M,Alg_Bprm,K,N,MR,R). % for_each_C(+ALGS_C,+HPRIME,+ALG_M,+ALG_BPRIME,+YS,+MAXRANK,-RANK) % If all subalgebras in the list, ALGS_C, are successfully % exhausted, RANK binds with the maximum rank, MAXRANK. Otherwise, % recursively traverse the list, ALGS_C, passing each subalgebra % in the list to there_exists_Y/7. for_each_C([] ,Hprm,Alg_M,Alg_Bprm,Ys,R,R). for_each_C([algebra(C,FC) IAlg_Cs] ,Hprm,Alg_M,Alg_Bprm,Ys,MR,R) list_to_ord_set(C,OC), ord_functions(FC,OFC), ! , there_exists_Y(Ys,algebra(OC,OFC) ,Alg_M,Alg_Bprm,Hprm,MR,TR), for_each_C(Alg_Cs,Hprm,Alg_M,Alg_Bprm,Ys,TR,R). % there_exists_Y(+YS,+ALG_C,+ALG_M,+ALG_BPRIME,+HPRIME,+RANK,-NEWRANK) % Recursively traverse the list argument, YS, of sets of % homomorphisms with known rank, searching for a set which % satisfies all the predicates in the tail of the second clause. % If a set does not satisfy all the predicates, move on to the % next set using the third clause. If no such set exists, cause 123 % a fail of the who le predicate by the first clause. there_exists_Y([] ,Alg_C,Alg_M ,Alg_Bprm ,Hprm,R, NewR) - ! , fail. there_exists_Y([YIYs] ,Alg_C,Alg_M,Alg_Bprm,Hprm,R,NewR) separates(Y,Alg_Bprm,Fact_Alg), factor_algebra(Alg_C,Y,Alg_Bprm,Fact_Alg,algebra(CmodY,FCmodY)), list_to_ord_s et(CmodY,OCmodY), ord_functions(FCmodY,OFCmodY), is_algebra(algebra(OCmodY,OFCmodY)), lifts(Hprm,algebra(OCmodY,OFCmodY) ,Alg_ M), for_each_ g(Y,R,NewR). there_exists_Y([YIYs] ,Alg_C,Alg_M,Alg_Bprm,Hprm,R,NewR) there_exists_Y(Ys,Al g _C,Alg_M,Alg_Bprm,Hprm,R,NewR). % for_each_g(+Y,+TEMPRANK,-MAXRANK) % Argument, TEMPRANK, is the largest value of rank for % homomorphisms, g, in argument list, Y, at any given time. % Recursively traverse the list, Y, until it is empty, at % which point MAXRANK binds with TEMPRANK. for_each_g ( [], R, R) . for_each_g([homomorphism(R,K,Alg_Mn,Alg_M,Homo) !Rest] ,TR,MR) R >= TR, ! , for_each_g(Rest,R,MR). for_each_g([GiGs] ,TR,MR) for_each_g(Gs,TR,MR). 124 /********************************************************************/ I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* FILE: make_ Mn.pl Creates the algebra, M to the nth power, an algebra, M, and integer, n. BY: CREATED: MODIFIED: Rich Little 16 March 1998 PREDICATES: make_M_to the_n l3 make_universe l 3 make_universe_more l 4 CALLED-BY: rank l 6, for _ each_k l 9, for each_i l 4 from *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I I******************************************************************** I % make_M_to_the_n(+ALG_M,+N,-ALG_MN) % Given an algebra argument, ALG_ M, and an integer argument, N, % construct the algebra, ALG_MN, the Nth power of algebra, ALG_M. make_M_to_the_n(algebra(M,FM) ,N,algebra(Mn,FMn)) make_universe(M,N,Mn), make_functions(FM,Mn,FMn). % make_universe(+SET_M,+N,-SET_MN) % Starts with set, SET_M, and counting up from 1 to N, builds each % set, M to the power i, until reaching the set, SET_MN, which is % SET_M to the power N. make_universe{M,N,Mn) - N =< 0, ! , fail. make_universe(M,1,M). make_universe(M,N,Mn) N1 is N - 1, make_uni verse(M,N1,TempMn}, make_universe_more(M,TempMn,TempMn,Mn) % make_universe_more(+SET_M,+SET_MI,+SET_MI,-SET_MN) % Recursively traverses the set, SET_M , and adds each element of SET M % to the end each element of the set, SET_MI, building the set, SET_MN. % One set argument, SET_MI, is used for traversing, while the other is % used as a starting point for each element in SET_M. rnake_universe_more ([) ,Set, Set,[)). make_universe_more([[X) !Rest),[) ,Set,Mn) make_universe_more(Rest,Set,Set,Mn). make_universe_more([[X) !Rest), [[YIRest1) 1Rest2) ,Set, [[X,Y1Rest1) 1Rest3)) make_universe_more([[X) !Rest) ,Rest2,Set,Rest3). 125 /********************************************************************/ I* I* FILE: subalgebra.pl Does one of three things. 1 Checks that I* ALG_B is a subalgebra of ALG_M, 2 generates I* ALG_B a subalgebra of given ALG_M, or 3 I* checks or generates ALG_D where ALG_B' is I* a subalgbera of ALG_D a subalgebra of ALG_M. I* I* I* BY: Rich Little I* CREATED: 4 Feb 1999 I* MODIFIED: 4 Mar 1999 (added subalgebral3) I* 7 Jan 2000 (added first clause of subalgebral3) I* I* I* PREDICATES: subalgebral3 I* gen_subalgebra l 3 I* subalgebral2 I* closed l 2 I* generate_subalgebra l 4 I* apply_each_fl4 I* apply_f l 4 make_functions listl3 I* make_function_list13 I* I* I* CALLED-BY: rank l 6, for_each_partl9, for_each_DI8, I* for_each_i l 4, is_algebra l 1 I* *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I !**************************************************** **************** / % subalgebra(+ALG_B' ,-ALG_D,+ALG_M) % If algebra argument, ALG_B', is the same as algebra argument, % ALG_M, then ALG_D binds with ALG_B'. Else, The algebra, ALG_D, is % generated such that ALG_D is a subalgebra of algebra, ALG_M, and % algebra, ALG_B', is a subalgebra of ALG_D. subalgebra(Alg,Alg,Alg), 1 subalgebra(Alg_Bprime,Alg_D,Alg_M) subalgebra(Alg_D,Alg_M), subalgebra( Alg_Bprime,Alg_D) . % gen_subalgebra(?X,-ALG_B,+ALG_M) % Generate the smallest subalgebra, ALG_B, of algebra, ALG_M, % that contains X. If X is a variable generate an arbitrary % subalgebra. gen_subalgebra(XO,algebra(B,FB) ,algebra(M,FM)) sublist(XO,M), generate_subalgebra(M,XO,FM,B), make_functi ons_list(FM,B,FB). 126 % subalgebra(?ALG_B,+ALG_M) % For a given algebra, ALG_B, checks if it is a subalgebra % of algebra, ALG_M. Otherwise, generate an arbitrary subalgebra % of algebra, ALG_M, which binds with ALG_B. subalgebra(algebra(B,FB ) ,algebra(M,FM)) sublist (B, M) , closed(B, FM), make_functions_list(FM,B,FB). % closed(+SET,+FM) Let FSET be the result of applying the functions of FM to the set, SET. SET is closed under FM if the union of SET and FSET equals SET. The empty set, [), does not generate a subalgebra. % % % % closed([),FM) : - ! , f a i l . closed(XN,FM) list_to_ord_set (XN,OrdXN), apply_each_f(FM,OrdXN, [) ,FXN), list_to_ord_set(FXN,OrdFXN), ord_union (O rdXN,OrdFXN,XNplusl), !, ord_seteq(OrdXN,XNplusl). % generate_subalgebra(+XN-l,+XN,+FM,-B) % The empty set generates the empty subalgebra which % is not considered an algebra. If the set, XN-1, is equal to % the set, XN , we are done and B binds to XN. Else, let XN+l be % the union of XN and the resulting set from applying FM to XN and recurse on XN and XN+l. % generate_subalgebra ( [) ,A,B,C) :- ! , fail. generate_subalgebra(XNminusl,XN,FM,XN) ord_seteq(XNminusl,XN) , 1 generate_subalgebra (XNminusl,XN,FM,B) list_to_ord_set(XN,OrdXN), apply_each_f(FM,OrdXN, [),FXN), list_to_ord_set(FXN, Or dFXN), ord_union( OrdXN ,OrdFXN,XNplusl), generate_subalgebra(OrdXN,XNplusl,FM,B), % apply_each_f(+F S,+X,+TEMP_FX,-FINAL_FX) % % !. Apply each function in the list, FS, the set, FINAL_FX. apply_each_f( [) ,X,FsX,FsX). apply_each_f ([FMIFMs) ,X,FMX,FMsX) apply_f(X,FM,FMX,TempFMX), apply_each_f (FMs , X,TempFMX,FMsX). 127 to the set, X, getting % apply_f(+XS,+F,+FXS,-NEW_FXS) % % % Apply the function, F, to each element in the set, XS, getting the set, NEW_FXS. Both lists, XS and F, are ordered, thus only one pass through both is necessary. apply_f([) ,FM,FMsX,FMsX). apply_f([XIXs ), [f(X,FMX) IFMs) ,FMsX, [FMXIFMXs)) apply_f(Xs,FMs,FMs X,FMXs). apply_f(Xs, [FMIFMs) ,FMsX,FMXs) apply_f( Xs,FMs,FMsX,FMXs). % make_functi ons_list( +FMS ,+B, ? FBS) % Construct the list of functions, FBS, where each % functi on in FBS is the restriction of the coo responding function in the lis t, FMS, to the set B. % make_functions_list([) ,B, [)). make_function s _li st([FMIFMs) ,B, [FBIFBs)) make_function_list(B,FM,FB), make_func t ions_list ( FMs,B,FBs), ! . % make_functi on_list(+B S ,+FM, ? FB) % % % For each element in list, BS, the result of applying the function, FB, to the element is equal to the result of applying the function, FM, to that element. make_function_list([) ,FM, [)) . make_function_list([BIBs), [f(B,FB) IFMs), [f(B,FB) IFBs)) make_function_list(Bs,FMs,FBs), ! . make_function_list( [BIBs), [FMIFMs) ,FBs) make_function_list ( [BIBs) ,FMs,FBs), ! . 128 /********************************************************************/ I* I * FILE: homomorphism.pl I* Tests for a homomorphism from an I* algebra B to an algebra M I* Rich Little I* BY : I * CREATED: l Nov 1999 (added header and documentation) I * MODIFIED: 2 Dec 1999 I* I* I * PREDICATES: homomorphism l 4 I* extend_homomorphisml5 I* gen_homo l 5 I* build_h l6 for_all f l 6 I* build_on_B I 5 I* preserves_operationsl3 I* for each_f l 4 I* I* I* CALLED-BY: lifts l3, is_homomorphism l1 I* *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I ! ********************************************* * ********************** / % homomorphism(algebra(+B,+FB) ,algebra(+M,+FM), [+DOMPH,+PH], [?DOMH,?H]) % If the list, B, e quals the list, DOMPH, and the homomorphism % [DOMPH,PH] preserves the functions, FB and FM, then [DOMH,H] binds % to the homomorphism, [DOMPH,PH]. Else, pick the next element % in the list resulting from subtracting DOMPH from B, and extend % the homomorphism. homomorphism(algebra(B,FB) ,algebra(M,FM), [H,HL], [H,HL]) ord_seteq(H,B), preserves_operations([H,HL] ,FB,FM). homomorphism(algebra(B,FB) ,algebra(M,FM), [H,HL], [NewH,NewHL]) ord_subtract(B,H, [NBINewB]), !, extend_homomorphism(NB,algebra(B,FB) ,algebra(M,FM), [H,HL] , [TH,THL]), homomorphism(algebra(B,FB) ,algebra(M,FM), [TH,THL], [NewH,NewHL]). % extend_homomorphism(+ELEMENTOF_B,+ALG_B,+ALG_M,+HOMO,-EXTENDED_HOMO) % If extension is possible, then extend the homomorphism on element, % ELEMENTOF_B and the first element of the universe of algebra, ALG_M. Else, recurse on ELEMENTOF_B and the next element of the universe % of ALG_M, binding with EXTENDED_HOMO. % extend_homomorphism(NB,algebra(B,FB) ,algebra([MIMs] ,FM), [H,HL], [NewH,NewHL]) ord_add_element(H,NB,NH), ord_add_element(HL,h (NB,M) ,NHL), gen_homo ([NH,NHL], [H,HL) ,algebra{B,FB) ,algebra( [MiMs) ,FM), [NewH,NewHL)) extend_homomorphism(NB,algebra(B,FB) ,algebra( [MIMs) ,FM), [H,HL), [NewH,NewHL]) extend_homo morphism(NB,algebra(B,FB) ,algebra(Ms,FM), [H,HL), [NewH,NewHL)). 129 % gen_homo(+HOMO_N+l, +HOMO_N,+ALG_B,+ALG_M,-HOMO) % If the list, HOMO_N+l, equals list, HOMO_N, HOMO_N+l binds % with HOMO. Else, extend the homomorphism on all the elements % in HOMO_N+l not in HOMO_N. Let HOMO_N+2 be the union of HOMO_ N+l % and HOMO_N. We recurse on HOMO_N+2 and HOMO_N+l. gen_homo([DHnpll,Hnpll], [DHn,Hn] ,algebra(B,FB) ,algebra(M,FM), [DHnpll,Hnpll]) ord_ seteq (Hnpll ,Hn), 1 gen_homo([DHnpll,Hnpll], [DHn,Hn] ,algebra(B,FB) ,algebra(M,FM) ,Homo) ord_subtract(Hnpll,Hn,TempH), !, build_H (TempH, [DHnpll,Hnpll] ,FB,FM, [[], []], [DNewH,NewH]) , ord_union(DHnpll,DNewH,DHnpl2), ord_union (Hnpll,NewH,Hnpl2), ! , gen_homo([DHnp l 2 ,Hnpl2 ], [DHnpll,Hnpll] ,algebra(B,FB) ,algebra(M , FM) ,Homo) . % build_H(+HOMO_Nl \ HOMO_N,+HOMO_Nl,+FUNCTION_B,+FUNCTION_M,+PART_HOMO,-GEN_ HOMO) % Recurse on the list of elements, HOMO_Nl \ HOMO_ N, in order to extend the % partial homomorphism, PART_HOMO. When the list, HOMO_Nl \ HOMO_N, is empty , % GEN_HOMO binds with PART_HOMO. build_H([] ,Homo,F B,FM,Homol,Homol). build_H( [XIXs ] ,HomoNl,FB,FM,PartHomo,GenHomo) ! , for_al l_f(X ,HomoNl,FB,FM,PartHomo,TempHomo), ! , build_H (Xs, HomoNl,FB,FM,TempHomo,GenHomo). % for_all_f(+H (X,Y) ,+HOMO_Nl,+FUNCTION_ B,+FUNCTION_M,+PART_HOMO,-NEW_ HOMO) % Recurse through the function lists, FUNCTIONLIST_B and FUNCT I ONLIST_ M, % applying each function of FUNCTOIN_B to the element, X, and applying % each fu nction of FUNCTION_M to the element, Y. for_all_f(Elem, HomoNl, [], [] ,H omo ,Homo). for_all_f(h(X ,Y) ,Hl, [FBIFBs], [FMIFMs] , Homo,NewHomo) find_f_of(X,FB,FofX), find_f_of(Y , FM,F o fY ) , !, build_on_B (FofX,FofY,Hl,Homo,THomo), !, for_all_f(h (X ,Y) ,Hl,FBs,FMs,THomo,NewHomo). % build_on_B(+NEWB,+NEWM, [+DPHl,+PHl], [+DPH2,+PH2], [-DNH,-NH]) % If element, NEWB, is already in the list, DPHl, and h(NEWB,NEWM) is in the list, PHl, t hen [DNH,NH] binds to homomorphism, [DPH2,PH2] . % Else, if NEWB is in list, DPH2, and h(NEWB,NEWM) is in list, PH2, % % then [DNH,NH] binds t o [DPH2,PH2] . Els e, add NEWB to DPH2 and add % h(NEWB,NEWM) to PH2 resulting in [DNH,NH]. build_on_B(NB,NM, [H,HL], [H l,HLl], [Hl,HLl]) member(NB,H), ! , member(h(NB,NM) ,HL). build_on_B(NB,NM, [H,HL], [Hl,HLl], [Hl,HLl]) member(NB,H l), ! , member(h(NB,NM) ,HLl). build_on_B(NB,NM, [H,HL], [Hl,HLl], [NewH l ,NewHLl] ) ord_ add_elemen t(HLl,h(NB,NM) ,NewHLl), ord_add_element(Hl,NB,NewHl). 130 % preserves_operations(+HOMO,+FB,+FM) % In order for HOMO to be a homomorphism, each function in the function % lists, FB and FM, must be preserved for each element in the domain % of HOMO. preserves_operations([[) ,Homo) ,FB,FM). preserves_operations([[XIXs) ,Homo) ,FB,FM) for_each_f(FB,FM,X,Homo), preserves_operations([Xs,Homo) ,FB,FM). % for_each_f(+FBS,+FMS,+X,+HOMO) % % % The functions in the function lists, FBS and FMS, are considered to be preserved if HOMO(FB(X)) equals FM(HOMO(X)) for each function FM ln FMS FB in FBS. for_each_f([), [) ,X,Homo). for_each_f([FBIFBs), [FMIFMs] ,X,Homo) find_f_of(X,FB,FBofX), find_h_of(FBofX,Homo,HofFBofX), find_h_of(X,Homo,HofX), find_f_of(HofX,FM,FMofHofX), ! , HofFBofX == FMofHofX, for_each_f(FBs,FMs,X,Homo). 131 /**************************************************************** **** / I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* FILE: partition_k.pl Partitions fixed K into a list of size N, by first creating the list [K,O, ... ,0], with N-1 O's, then giving it the tag [1]. The tag represents the rightmost nonzero position in the list. The next stage is to take the first partition and make new ones by creating the list [K-i,i , O, .. . ,0] for each i less than or equal to K, until K=O. Then we do the same for each of these in the 2 position, and so on until tag=N. BY: CREATED: MODIFIED: Rich Little 30 April 1998 7 Jan 2 00 0 (built-in append l 3 replaced conc l 3) PREDICATES: partition_k l 3 first_partition l 4 rest _ of_partitions l 3 build_on_partition l 5 new_partitions l 2 put_stripped_backl3 add_tag l 3 lose_tag l 2 CALLED-BY: for each_kl9 *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I /********************************************************************/ % partition_k(+K,+N,-LISTOFPARTITIONEDK) Partition the integer, K, into a list of size N, binding with the argument, LISTOFPARTITIONEDK. % % partition_k(K,N,NewKLists) first_par tition(K,N,N,KList) , rest_of_partitions([KList] ,N,KLists), lose_tag(KLists,NewKLists). % first_partition(+K,+N,+COUNTER,-FIRSTPARTITION) Build a list, [K,O, . .. ,0] with N-1 O's, and % add the tag [1], getting a list of 2 lists, % [[1], [K,O, ... ,0]] which binds with argument, % FIRSTPARTITION. The argument, COUNTER, is used to % get the number of O's needed . % first_partition(K,N,O, []). first_partition(K,N,N, [ [1], [KiKs]]) Nl is N-1, first_partition(K,N,Nl,Ks). 132 first_partition(K,N,N1, [OIKs]) N2 is Nl-1, first_partition{K,N,N2,Ks). % rest_of_partitions(+PARTITIONS,+N,-EXTENDEDPARTITONS) % For each partition in list, PARTITIONS, build on it % by pulling out the first element, adding it to the list, % EXTENDEDPARTITIONS, and then passing it to build_on_partition/5. % Add the new partitions onto the end of PARTITIONS and run % through it recursively until it is an empty list. rest_of_partitions([] ,N, []). rest_of_partitions([KListiR1] ,N, [KListiR2]) build_on_partition(KList,N,1,Stripped,TempKList), put_stripped_back(Stripped,TempKList,NewTempKList), append(R1,NewTempKList,NewKList), rest_of_partitions(NewKList,N,R2). % build_on_partition( [+TAG,+PARTITION] ,+N,+COUNTER,+STRIPPED,-BUILT) % When tag, TAG, equals N, the partition PARTITION can no longer be % b u ilt on. Otherwise, use COUNTER to move through PARTITION to get % to the tag position, ie tag=COUNTER. Then make the new partitions % and add their tags. build_on_partition([[N] ,List] ,N,1, [], []). build_on_partition([[M], [ F1,F2IR1]] ,N,M, [] ,NewKList) new_partitions([F1,F2IR1] ,KList), M1 is M+1, add_tag(M1,KList,NewKList). build_on_partition([[M], [F1,F2IR1]] ,N,M1, [F1IR2] ,R3) M2 is M1+1, build_on_partition( [[M], [F2IR1]] ,N,M2,R2,R3). % new_partitions(+PARTITION,-NEWPARTITIONS) % Subtract 1 from the first element of list, PARTITION, % % and add 1 to the second element of list, PARTITION, ~ until the first element is 0. new_partitions([OIR1], []). new_parti tions ( [ F1, F2 I R1] , [ [ F3, F41 R1] I R2] ) F3 is F1-1, ' F4 is F2+1, new_partitions([F3,F4IR1] ,R2). % put_stripped_back(+STRIPPED,+EXTPARTITIONS,-PARTITIONS) When we extend our partitions, we move through % the old partition to get to the tag position. % As we do this, we strip off the front of the list. % We put the stripped off partitions back on to the new % list, EXTPARTITIONS, binding with PARTITIONS. % 133 put_stripped_back([] ,List,List). put_stripped_back(List, [] , []). put_stripped_back(List, [[Tag,Listl] IRl], [[Tag,List2] IR2]) append(List,Listl,List2), put_stripped_back(List,Rl,R2). % add_tag(+TAG,+NEWPARTITIONS,-TAGGEDPARTITIONS) % Recursively traverse the list, NEWPARTITIONS, % the element, TAG, at the head of each list. inserting add_tag(Tag, [], []). add_tag(Tag, [ListiRl], [[[Tag] ,List] IR2]) add_tag(Tag,Rl,R2). % lose_tag(+TAGGEDPARTITIONS,-PARTITIONS) % The argument, PARTITIONS, binds with the list, % TAGGEDPARTITIONS, after the first element in each list % of TAGGEPARTIOTNS is removed . lose_ tag ( [ l , [ l ) . lose_tag( [ [Tag,ListliRl], [ListiR2]) lose_tag (Rl,R2). 134 /********************************************************************/ !* !* !* FILE: embed_B.pl /* !* !* !* !* /* /* !* !* !* /* !* !* !* BY: CREATED: MODIFIED: Using an algebra, B, and a fixed finite K, create an algebra, B', by repetition of coordinates. Rich Little 7 April 1998 PREDICATES: embed_B / 3 rep_coords/3 rep_coords_each/3 CALLED-BY: for_each_part / 9 *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I ! ******************************************************************** / % embed_B(+ALGEBRA_B,+K,-ALGEBRA_B_PRIME) % Embed algebra argument, ALGEBRA_B into an algebra by repetition % of coordinates for finite integer argument, K. The new algebra % binds with the uninstantiated argument, ALGEBRA_B_PRIME. embed_B(algebra(B,FB) ,K,algebra(Bprime,FBprime)) rep_coords(B,K,Bprime), make_functions(FB,Bprime,FBprime). % rep_coords(+SET_B,+K,-SET_B_PRIME) % Walk the list, SET_B, of element lists, applying the same % repetition of coordinates, K, to each. The new list binds % with SET_B_PRIME. rep_coords([] ,K, []). rep_coords([XjRest] ,K, [YjRest1]) rep_coords_each(X,K,Y), rep_coor ds(Rest,K,Rest1). % rep_coo r ds_each(+ELEMENT_OF_B,+K,-ELEMENT_OF_B_PRIME) % The argument, K, is represented by a list of the same % size as the element list, ELEMENT_OF_B. The elements of the % list, K, are integers which. A 0 in the list means you do % not repeat the cooresponding coordinate in ELEMENT_OF_B, % (clause 3), a 1 means one copy of the coordinate , etc, % (clause 2) . rep_coords_each( [], [], []) rep_coords_each([X jRest], [KjRest1], [X,XjRest2]) K > 0, !, K1 is K-1, 135 rep_coords_each( [XIRest), [KliRestl), [XIRest2)). rep_coords_each([XIRest), [OIRestl) , [X1Re s t 2)) rep_coords_each(Rest,Restl ,Rest2). 136 /******************************************************************* * / I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* FILE: li fts.pl Tests for lifting between an algebra, D, or factor algebra, CIY to an algebra, M. BY: CREATED: MODIFIED: Rich Little 16 Jan 1999 PREDICATES: lifts 1 3 make_mew l 3 find_X I 3 CALLED-BY: for_each_D I 8, there_exists_Y I 7 *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I !* ******************************************************************* / % lifts(+HPRI ME,+ALG,+ALG_M) % % % % A homomorphism, HPRIME, lifts to an algebra, ALG, if there exists a homomorphism, mew, from ALG to an algebra, ALG_M, extended from the natural homomorphism, i, from an algebra, B', to ALG such that mew(x) = h' (x), for all x in B'. lifts([DomHprime,Hprime ] ,Alg_D,Alg_M) make_mew(Hprime,Alg_D,PartHomo), homomorphism(Alg_D,Alg_M,PartHomo,Homo) % make_mew(+HPRIME,+ALG,-PART_HOMO) Construct a potential partial homomorphism which binds with % the uninstantiated argument, PART_HOMO. % make_mew([] ,Alg_D, [[], []]). make_mew([h(X,Y) !Rest] ,Alg_D, ([IofXIRest1], [h(IofX,Y) 1Rest2]]) find_X(X,Alg_D,I ofX), make_mew(Rest,Alg_D, [Res t1,Rest2]). % find_X(+X,+ALG,-I OFX) If element, X, is the next element of algebra, ALG, then IOF binds with X. Else, X is an element of the next class of factor % algebra, ALG, then IOFX binds with that class. Else, recurse % on the elements of ALG. % % find_X(X,algebra([XiXs] ,FL) ,X). find_X(X,algebra ([[Tag,List] !Rest] ,FL), [Tag,List]) member(X,Lis t). find_X(X,algebra([Y iYs] ,FL) ,IofX) find_X(X,algebra(Ys,FL) ,IofX) 137 I******************************************************************** I I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* FILE: get_Ys.pl BY: CREATED: MODIFIED: Retrieves relevant homomorphisms from the database of homomorphisms with known rank. Rich Little 19 Feb 1999 28 Jul 1999 (changed dBase to atoms) PREDICATES: get_Ys l 5 get_Ys l6 sizeof_g_lessthan_NI3 find_gs l6 CALLED-BY: *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I ! ******************************************************************** / % get_Ys(+ALG_M,+ALG_MN,+K,+N,-LISTOFYS) % When using get_Ys l 5, it is assumed that the database of algebraic % operations of an algebra, ALG_M, with known rank are asserted as % facts in the system. All instances of homomorphisml5 with % arguments K, ALG_M, and ALG_MN are collected in an ordered set. % The order of this set is based on the rank of the homomorphisms. % Reverse the order of this set then collect all instances of % sublists of the set in an ordered set. Each sublist is ordered % from maximum rank to minimum.Finally, remove all the sublists % that are stictly larger than N. get_Ys(M,Mn,K,N,Ys) setof(homomorphism{R,K,Mn,M,H) ,homomorphism(R,K,Mn,M,H) ,Gs), reverse(Gs,RGs), setof(G,sublist(G,RGs) ,Zs), sizeof_g_lessthan_N(Zs,N,Ys) % get_Ys(+ALG_M,+ALG_MN,+K,+N,+FILE,-LISTOFYS) % The predicate, get_Ys l 6, does the same thing as get_Ysl5 except that % the algebraic operations of ALG_M with known rank are stored in % readable source file, FILE. get_Ys(Alg_M,Alg_Mn,K,N,File,Ys) open(File,read,Stream), read(Stream,Term), find_gs(Term,Stream,K,Alg_M,Alg_Mn,Gs), close(Stream), list_to_ord_set(Gs, OGs), reverse(OGs,RGs), setof{G,sublist(G,RGs) ,Zs), sizeof_g_lessthan_N (Zs ,N,Ys) 138 % sizeof_g_lessthan_N(+LIST,+N,-WANTED_LIST) % Recursively remove all the elements of the list , LIST , that are % strictly larger than integer, N. The resulting list binds with % the argument, WANTED_LIST. sizeof_ g _ lessthan_N([] ,N, []). sizeof_ g_lessthan_N([Z!Zs] ,N, [Z!Ys]) count(Z,M ) , M = < N, M > 0, sizeof_g_lessthan_N(Zs,N,Ys). sizeof_ g _ lessthan_N([Z!Zs] ,N,Ys) sizeof_g_lessthan_N(Zs,N,Ys). % find_ gs(+TERM,+STREAM,+K,+ALG_M,+ALG_MN,-GS) % Search the database attached to stream, STREAM , keeping only the % homomorphisms from algebra, ALG_ MN, to algebra, ALG_M , for some, K. % The resulting list binds with argument, GS. find_ gs(end_of_file,S,K,M,Mn, []). find_ gs(homomorphism(R,K,Mn,M,H) ,S,K,M,Mn, [homomorphism(R,K,Mn,M,H) !Rest]) read(S,Term), find_gs(Term,S,K,M,Mn,Rest) . find_ gs(Terml,S,K,M,Mn,List) read(S , Term2), find_gs(Term2,S,K,M,Mn,List). 139 /********************************************************************/ I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* FILE: separates.pl BY: CREATED: MODIFIED: Checks if a set, Y, of homomorphisms from an algebra, D, to an algebra, M, separates an algebra, B' . Rich Little 2 Jan 1999 19 Feb 1999 (removed get_Ysl4, PREDICATES: separatesl3 separatedl1 CALLED BY: there_exists_YI7 ln its own file) *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I /********************************************************************/ % separates(+Y,+ALGEBRA_BPRIME,-UNIVERSE_BPRIMEMODY) % Checks that the set of homomorphisms, Y, separates an algebra, % ALGEBRA_BPRIME, by constructing the universe of the factor algebra % of ALGEBRA_B with respect to Y. If the factor algebra is separated, % then argument, UNIVERSE_BPRIMEMODY, binds to the factor universe. separates(Y,algebra(BPrm,FBPrm) ,Fact_Uni) factor_universe(BPrm,Y, [) ,Fact_Uni), ! , separated(Fact_Uni). % separated(+FACTORALGEBRA) The factor algebra, FACTORALGEBRA, is considered to be separated if each class in the algebra contains only one element. Done recursively on the classes of the factor algebra. % % % separated ( [)) . separated ( [[Tag,Class) !Rest)) count (Class,C), ! ' c == 1' separated(Rest) 140 /********************************************************************/ I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* I* FILE: factor_algebra.pl Builds a factor algebra, C I Y, given an algebra, C, and a list of homomorphisms, Y. BY: CREATED: MODIFIED: Rich Little 2 Jan 1999 22 Feb 1999 (changed factor_universe l 4) (added apply_Y I 3) PREDICATES: factor_algebral5 factor_universe l 4 for each_functionl3 factor_function l 4 apply_Y I 3 add_element l 4 in_class l 3 CALLED-BY: there exists Yl 7 *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I ! ******************************************************************** / % factor_al gebra(+ALG_C,+Y, +ALG_BPRIME,+BPRIME I Y,-ALG_CIY) % Creates the factor algebra of an algebra, ALG_C , with respect % to the homomorphism list, Y, and binds it to the argument, ALG_CIY. % The argument, ALG_BPRIME , represents a subalgebra of ALG_C % which has a universe that has been previously factored as, BPRIMEIY. factor_algebra(algebra(C,FC) , Y,algebra(Bprm,FBprm) ,BprmY,algebra(CY ,FCY)) ord_subtract(C,Bprm,RestofC), factor_universe(RestofC,Y,BprmY,CY), for_each_function(CY,FC,FCY). % factor_uni verse(+UNI_C \ UNI _ BPRIME ,+Y,+UNI _BPRIME I Y,-UNI_C I Y) % Recurse through the list of elements, UNI_C\UNI _BPRIME, % applying the set of homomorphisms, Y, to each element in % order to add each element to the appropriate class. The % argument, UNI_C I Y, binds to the list, UNI_BPRIME I Y, once % all the elements are the appropriate class. factor_universe([] ,Y,Universe,Universe). factor_universe([XiXs] ,Y,Universe,NewUniverse) apply_Y(Y,X,Tag), add_element(X,Tag,Universe,TempUniverse), factor_universe(Xs,Y,TempUniverse,NewUniverse) % for_each_function(+UNI_C I Y,+FUNCTIONLIST_C,-FUNCTIONLIST_CIY) For each function in the function list, FUNCTIONLIST_C, % % create the corresponding function for the factor algebra % with underlying universe, UNI_C I Y, binding with FUNCTIONLIST_CIY. 141 for_each_fun ction(CmodY, [], []). for_each_fun ction(CmodY, [FI Fs ] , [FCmodY IFCmodYs]) factor_functi on(CmodY,Cmo dY, F,FCmodY), for_each_f unct i on(CmodY,Fs ,FCmodYs). % factor_func tion(+UNI _ C/ Y,+UNI_C/Y,+FUNCTION_C,-FUNCTION_C/Y) Recurse on list, UN I_C/ Y, the uni ve rse o f a factor algebra, in order to create the function list which cor responds to this factor universe, which binds with the argument, FUNCTION_C/Y. % % % factor_functi on( [] ,UniCY ,FC, []). factor_functi on([[Tag, [XIXsl l iRLUn iCY,FC, [f([Tag, [XIXs]],Class) IRl]) find_f_ of(X,FC,FofX), in_class (FofX,UniCY , Class), fact o r_functi on(R,UniCY, FC,Rl) % apply_Y(+ Y, +X,-TAG) % Recur sively apply each homomorphism in a list, Y, to an element, X, resulting in a lis t which binds with argument TAG, to be used % % as a key for the cl as se s of a factor algebra. apply_Y( [],X,[]). apply_Y([homomo rphis m(Rank ,K,Alg_Mn,Alg_M, [Dom,Homo]) IGs] ,X, [GofXIRest]) find_h_of (X,Homo , GofX) , apply_Y(Gs,X,Rest). % add_elemen t( +ELEMENT,+TAG,+UNIVERSE,-NEWUNIVERSE ) If class with key name, TAG, does not exist, then create it, % % add the element , ELEMENT, to that class and add that class to % the list, UNIVERSE, binding it with NEWUNIVERSE. Else, add ELEMENT % to the appropriate class by recursing on the elements (classes) of % argument, UNIVERS E, binding the resulting list with NEWUNIVERSE. add_element (Element,Tag, [] ,([Tag, [Element]]]). add_element(Element,Tag, [[Tag,Class] !Rest], [[Tag, [ Element iC lass]] !Rest]) add_element(Element,Tag, [ClassiClasses], [Class iC la ss esl]) add_e l ement(Element,Tag,Classes,Classesl). % in_class(+ELEMENT,+UN I_C/ Y,-CLASS) % If the element, ELEMENT, does not belong to list in the list, UNI_C / Y, then in_cl ass /3 fails. Else, recurse on UNI_C/Y, until % % the class list containing ELEMENT is found and is bound to argument, % CLASS. in_class(Elemen t,[ ],Class) : - ! , f a i l . in_class (Element, [ [Tag,ClassliRest] , [Tag,Class ]) member (Element, Class) , ! . in_class(Element, [CiassiClasses] ,EqClass ) in_class(Element,Classes,EqClass). 142 /* *******************************************************************/ *I / * /* I* I* / * I* I* I* /* /* I* I* / * I* / * /* I* I* I* I* FILE: make_projections.pl Creates a database of clauses for the predicate, homomorphism/5, which consists of projections, which have rank less than or equal to zero. BY: CREATED: MODIFIED: Rich Little 12 Feb 1999 PREDICATES: make_projections/4 f or each_i/4 for_each_sub/4 for_each_j/5 projections /3 CALLED-BY: *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I *I ! ********************* ************************************** ********* / % make_projections(+ALG_M,+I,+K,+FILE) % Create a database of projections from subalgebras of finite % powers o f algebra, ALG_M, to ALG_M, for 1 < = I <= K. Store the % database as a file with filename, FILE. make_projections(algebra(M,FM) ,I,K,File) open(File1,write,Stream), list_to_ord_set(M,OM), ord_functions(FM,OFM), for_each_i(algebra(OM,OFM) ,K,I,Stream), close (Stream) . % for_each_i(+ALG_M,+K,+I,+STREAM) % For each integer, I, from 1 to some integer, K, construct the Ith % power of algebra, ALG_M, and collect all the subalgebras % of the resulting algebra. for_each_i(Algebra_M,K,I,Stream) I=