###################################################################### ## TENverbose: Save this file as TENverbose. To use it, # ## stay in the # ## same directory, get into Maple (by typing: maple ) # ## and then type: read TEN: # ## Then follow the instructions given there # ## # ## Written by Vince Vatter and Doron Zeilberger # ## Rutgers University , # ## [zeilberg,vatter] at math dot rutgers dot edu. # ###################################################################### with(combinat): print(`This is TENverbose, A Maple package, written by Vince Vatter`): print(`and Doron Zeilberger`): print(`It is a verbose version of TEN`): print(`accompanying the article: "A Computer-Generated(!) `): print(`Proof of the Amazing Loehr-Warrington TEN to the Power n Conjecture"`): print(` by S. B. Ekhad, V. Vatter, and D. Zeilberger`): print(`available from the authors' websites.`): print(): print(`First Written: Aug.-Sept. 2005. Tested for Maple 10. `): print(`Version of Sept. 21, 2005. `): print(): print(): print(`The most current version is available on WWW at:`): print(` http://www.math.rutgers.edu/~zeilberg/tokhniot/TEN .`): print(`Please report all bugs to: zeilberg at math dot rutgers dot edu .`): print(): print(`For general help, and a list of the MAIN functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): print(`For a list of the supporting functions type: ezra1();`): print(` For specific help for these also type "ezra(procedure_name);" `): print(): ezra1:=proc() if args=NULL then print(` The supporting procedures are: Aab, BetterTree,BuildTree, CHT, `): print(` CLONE, CF32, DescribeGrammar`): print(` EmpiricalClones, FattenUp32, FattenUp32aL, FattenUp32aLS, `): print(`ImpliedFactorization`): print(` LeftOvers32, Mishaps`): print(` PossiblePairs , PossibleGoodPairs, PotentialMishaps, `): print(` ProveCloneship32, ProveCloneship32v `): print(`ProveEmpty32, ProveEmpty32v, ProveEmpty32vv,`): print(` ProveVertexInclusion32 , `): print(` SpellOut, SR132, SurvivorsE32, TestProveEmpty32, WeedOut ` ): print(`For help with a specific procedure, type "ezra(procedure_name);"`): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(` TEN: A Maple package for Studying (in particular enumerating)`): print(` Loehr-Warrington words `): print(`The MAIN procedures are: DiscoverGrammar,`): print(` DiscoverGrammarVerbose, Corpus, `): print(` GFgrammar, LWwords , ProveGrammar32 , ProveGrammar32v`): print(` `): elif nargs=1 and args[1]=Aab then print(`Aab(a,b,n): simply LWwords(a,b,(a+b)*n,0)`): print(`For example, try: Aab(3,2,3); Aab(1,1,5);`): elif nargs=1 and args[1]=BetterTree then print(`BetterTree(C,a,b,T): Given a Corpus C, of a language in {a,-b} and `): print(`a tree T as a five-tuple`): print(`[Internals,CommitedLeaves,TempLeaves,ChildrenTable,Root]`): print(`picks one of the temporary leaves and finds its best children`): print(`making two new leaves and turing it into an internal vertex`): print(`For example,try: BetterTree(Corpus(3,2,3,0),3,2,IniTree([[],[]]));`): elif nargs=1 and args[1]=CleanUp then print(`CleanUp(S,a,b): Cleans up a set of words S in {a,-b}`): print(`from all the words that contain a zero-factor or a mishap`): elif nargs=1 and args[1]=DiscoverGrammar then print(`DiscoverGrammar(a,b,Len1): Discovers a `): print(`(conjectured) grammar for Loehr-Warrington `): print(`language in alphabet {a,-b}. `): print(`(This is the set of words in {a,-b} that sum to zero `): print(`and avoid any factor of the form`): print(`a[-a](-b) where [-a] denotes any word that sums to -a),`): print(`using a corpus of length Len1.`): print(`The output grammar is represented as a list of length 2: G=[T,S].`): print(`Here T is the family tree whose root is the vertex [[],[]], `): print(`and S is the subset of the set of internal vertices of T [w1,w2]`): print(`for which w1w2 belongs to the language.`): print(`The first component of G, the tree itself is represented as `): print(` pair [T1,T2]`): print(`where T1 is in charge of the internal vertices and T2 is in `): print(`charge of the leaves`): print(`T1 is represented as a list each of its entries has the form `): print(`[v, SetOfChildrenOf(v)]`): print(`where, of course SetOfChildrenOf(v) always has two elements `): print(` that are vertices`): print(`T2 is represented as a list, each of whose `): print(` entries is a pair [v,CloneOf(v)]`): print(`where v is a leaf and CloneOf(v) is either the empty set `): print(` ({}) or some internal vertex`): print(``): print(` For example, try: `): print(`DiscoverGrammar(1,1,3);, and Ta-Ta`): print(`DiscoverGramamr(3,2,3); `): elif nargs=1 and args[1]=DiscoverGrammarVerbose then print(`DiscoverGrammarVerbose(a,b,Len1): Discovers Verbose rendition ofa `): print(`DiscoverGrammar(a,b,Len1); (q.v.))`): elif nargs=1 and args[1]=BuildTree then print(`BuildTree(C,a,b): Given a corpus C in the alphabet {a,-b} `): print(`builds a good family tree. For example, try:`): print(`BuildTree(Corpus(1,1,4,0),1,1);`): elif nargs=1 and args[1]=CHT then print(`CHT(S,V):Given a set S of words, and a vertex V=[H,T]`): print(`with H and T words,`): print(`finds the set of all words in S that`): print(`starts with H and`): print(`ends with T and returns that set with H and T chopped`): print(`For example, try:`): print(`CHT(Aab(1,1,5),[[-1],[-1]]);`): elif nargs=1 and args[1]=CLONE then print(`CLONE(Corp1,V): Given a Corpus Corp1, and a `): print(`vertex V=[Prefix,Suffix], finds`): print(`its clone (another vertex or the empty set), or returns FAIL`): print(`For example, try: CLONE(Corpus(1,1,4,0),[[-1],[1]]);`): elif nargs=1 and args[1]=Corpus then print(`Corpus(a,b,Len,Sum1): The sequence of LW-words of `): print(` length (a+b)*i+Sum1 mod (a+b)`): print(`for i=0..Len. For example, try`): print(`Corpus(3,2,3,0);`): elif nargs=1 and args[1]=CF32 then print(`CF32(A): All the Conceivable Factorizations`): print(`using the ordinary letters 3 and -2 and the meta-letter [1]`): print(`in {3,-2} that sums-up to A, that has no zero-factors`): print(`and no mishaps`): print(`For example, try:`): print(`CF32(4);`): elif nargs=1 and args[1]=DescribeGrammar then print(`DescribeGrammar(G): Verbose description of the grammar G`): print(`For example, try: DescribeGrammar(DiscoverGrammar(1,1,3));`): elif nargs=1 and args[1]=EmpiricalClones then print(`EmpiricalClones32(a,b,V,m,n): Given a vertex B in the L-W `): print(` language {a,-b}`): print(` finds all the vertices with the same sum and length (a+b)*m longer`): print(`that seem to be clones of V using the corpus of words of `): print(` length<=n(a+b)`): print(`followed by the non-clones. `): print(`For example, try: EmpiricalClones(3,2,[[],[]],1,3);`): elif nargs=1 and args[1]=FattenUp32 then print(`FattenUp32(S):Given a set of words S in {3,-2,[1]}, `): print(`For each word, replaces it by the`): print(`triple obtained by replacing the first [1] by SR132()`): print(`For example, try: FattenUp32({[[1]]});`); elif nargs=1 and args[1]=FattenUp32aL then print(`FattenUp32aL(Lw):Given a list of words Lw in {3,-2,[1]}, `): print(`For each word, replaces it by the`): print(`triple obtained by replacing the first [1] by SR132()`): print(`For example, try: FattenUp32aL([[[1]]]);`); elif nargs=1 and args[1]=FattenUp32aLS then print(`FattenUp32aLS(SLw): Given a set of lists of words, gives the union `): print(`of the fattened versions`): print(`For example, try: FattenUp32aL({[[[1]]]});`); elif nargs=1 and args[1]=GFgrammar then print(`GFgrammar(G,x): The weight-enumerator for the language `): print(` generated by grammar G`): print(`in the variable x`): elif nargs=1 and args[1]=ImpliedFactorization then print(`ImpliedFactorization(a,b,Vert,,pm): `): print(`Given a vertex Vert=[P1,S1], where P1, S1 are`): print(`two words in {a,-b}`): print(`and a potential mishap pm=[i,j], say, find the implied factorization`): print(`as word in {a,-b} and [A]'s where [A] means a word whose sum is A`): elif nargs=1 and args[1]=IsGarbage then print(`IsGarbage(w,a,b): given a word w, decides whether it is garbage`): print(`either because it has a mishap, or because it has a zero-factor`): elif nargs=1 and args[1]=IsGarbageM then print(`IsGarbageM(w,a,b): given a word w, decides whether it is garbage`): print(`because it has a mishap`): elif nargs=1 and args[1]=IsGarbageZ then print(`IsGarbageZ(w,a,b): given a word w, decides whether it is garbage`): print(`because it has a proper zero-factor`): elif nargs=1 and args[1]=LeftOvers32 then print(`LeftOvers32(SetOfWordLists,ListOfFixedWords,i): `): print(`The set of left-overs `): print(`after i purges`): print(`For example, try:`): print(`LeftOvers32({[ [[1]]] },[[],[]],2);`): elif nargs=1 and args[1]=LWwords then print(`LWwords(a,b,Len1,Sum1): all the words in {a,-b} `): print(`of length Len1 that sum to Sum1 and`): print(`avoid a factor of the form a[-a](-b)`): print(`(Here [A] means a word that adds up to A)`): print(`For example, try: LWwords(3,2,10,0); LWwords(1,1,6,-2);`): elif nargs=1 and args[1]=Mishaps then print(`Mishaps(w,a,b): given a word w in {a,-b} finds its set of mishaps`): print(`For example, try: Mishaps([1,-1,-1,1],1,1);`): elif nargs=1 and args[1]=PossiblePairs then print(`PossiblePairs(Alph1,Len1,Sum1): all the possible pairs `): print(`[V1,V2] in the alphabet Alph1 such`): print(`that nops(V1)+nops(V2)=Len1 and Sum(V1)+Sum(V2)=Sum1`): print(`For example, try: PossiblePairs({3,-2},5,0);`): elif nargs=1 and args[1]=PossibleGoodPairs then print(`PossiblePairs(a,b,Len1,Sum1): all the possible pairs `): print(`[V1,V2] in the alphabet {a,-b} such`): print(`that nops(V1)+nops(V2)=Len1 and Sum(V1)+Sum(V2)=Sum1, `): print(` and V1 and V2 contain no mishaps`): print(`For example, try: PossiblePairs(3,2,10,0);`): elif nargs=1 and args[1]=PotentialMishaps then print(`PotentialMishaps(a,b,Vert): Given a vertex Vert=[P1, S1], `): print(`where P1 and S1 are (represented as lists) in the alphabet {a,-b}`): print(`prefix P1 and a suffix S1, returns all the location`): print(` of pairs [i,j] (where the middle`): print(`is also a location) that has an a in P1 or a -b `): print(`For example, try: PotentialMishaps(3,2,[[-2,3,-2,-2,-2],[3,3,-2]]);`): elif nargs=1 and args[1]=ProveCloneship32 then print(`ProveCloneship32(V1,V2,K): `): print(`Is Vertex V1 a clone of vertex V2, provable in K purges?`): elif nargs=1 and args[1]=ProveCloneship32v then print(`ProveCloneship32v(V1,V2,K): `): print(` Verbose version of ProveCloneship32(V1,V2,K) (q.v.) `): elif nargs=1 and args[1]=ProveEmpty32 then print(`ProveEmpty32(V,i): Finds out whether the vertex V`): print(`in the family-tree of the grammar for the {3,-2} Loehr-Warrington`): print(`language is empty after i purgings`): print(`For example, try: ProveEmpty32([[],[-2,3,-2,-2,-2,3]],2);`): elif nargs=1 and args[1]=ProveEmpty32v then print(`ProveEmpty32v(V,i): Verbose version of ProveEmpty32(V,i) `): print(`For example, try: ProveEmpty32v([[],[-2,3,-2,-2,-2,3]],2);`): elif nargs=1 and args[1]=ProveEmpty32vv then print(`ProveEmpty32vv(V,i): Very Verbose version of ProveEmpty32(V,i) `): print(`For example, try: ProveEmpty32v([[],[-2,3,-2,-2,-2,3]],2);`): elif nargs=1 and args[1]=ProveGrammar32 then print(`ProveGrammar32(T,K): `): print(`Tries to rigorously prove that the grammar G=[T,S] is a good tree, `): print(`i.e. its Clones are`): print(`as stated using K purgings, for example, try:`): print(`G:=DiscoverGrammar(3,2,3): ProveGrammar32(G,3);`): elif nargs=1 and args[1]=ProveGrammar32v then print(`ProveGrammar32v(T,K): `): print(`Verbose version of ProveGrammar32(T,K). For example try:`): print(`G:=DiscoverGrammar(3,2,3): ProveGrammar32v(G,3);`): elif nargs=1 and args[1]=ProveVertexInclusion32 then print(`ProveVertexInclusion32(V1,V2,K): Given two vertices, V1, V2`): print(`in {3,-2} proves that `): print(`if V2[1]wV2[2] is good then so is V1[1]wV1[2]`): print(`or equivalently,`): print(`if V1[1]wV1[2] is bad then so is V2[1]wV2[2]`): print(`by using K purgings`): print(`For example, try:`): print(`ProveVertexInclusion32([[],[3,-2,3,-2,3,-2,-2]],[[],[3,-2]],2);`); elif nargs=1 and args[1]=SpellOut then print(`SpellOut(ListOfWords,ListOfSets): Given a list of concrete `): print(`words ListOfWords,`): print(`and a list of sets of words, ListOfWords, `): print(`returns the set of all words`): print(`of the form `): print(`ListOfWords[1]ListOfSets[1][i1]ListOfWords[2]ListOfSets[2][i2]...`): print(`ListOfWords[nops(ListOfWords)]`): print(`For example, try:`): print(`SpellOut([[],[]],[{[2]}]);`): elif nargs=1 and args[1]=SR132 then print(`SR132(): The Self-Referential representation of [1] in terms of`): print(`itself (in the {3,-2} language)`): elif nargs=1 and args[1]=SurvivorsE32 then print(`SurvivorsE32(V,i): Given a vertex V finds the`): print(`survivors after the i-th purge`): print(`For example, try: Survivors32([[],[-2,3,-2,-2,-2,3]],2);`): elif nargs=1 and args[1]=TestProveCloneship32 then print(`TestProveCloneship32(V,m,n,K): Tests ProveCloneship32 for all`): print(`vertices similar to V, after K prunings`): print(`For example, try:TestProveCloneship32([[],[]],1,3,K);`): elif nargs=1 and args[1]=TestProveEmpty32 then print(`TestProveEempty32(L,Len1,Sum1,K): `): print(`tests ProveEmpty32(V,K) for words of length 10*L`): print(`and vertices of sum Sum1 and length Len1`): print(`e.g. TestProveEmpty32(3,8,4,3)`): elif nargs=1 and args[1]=WeedOut then print(`WeedOut(SetOfWordLists,ListOfFixedWords,a,b):`): print(`Given a set of word-lists (in the `): print(`letters a,-b, and the meta-letters [1]. ..[b-1]) and a list`): print(`of fixed words (in the alphabet {a,-b}} kicks out those word-lists`): print(`for which the word obtained by inserting the words of `): print(`the word-list between`): print(`consecutive members of the ListOfFixedWords contains mishaps`): print(`For example, try:`): print(`WeedOut({[-1]},[[1],[-1]],1,1)`): elif nargs=1 and args[1]=WhichPair then print(`WhichPair(C,a,b,V): Given a corpus C in the alphabet {a,-b} and`): print(`a vertex V, decides which pair of sons to make heirs`): print(`For example, try: WhichPair(Corpus(1,1,4),1,1,[[],[]]);`): else print(`There is no such thing as`, args): fi: end: Aab:=proc(a,b,n) Walks(a,b,b*n,a*n):end: with(combinat): IsBad:=proc(w,a) local i: for i from 1 to nops(w) do if w[i]=a and convert([op(i..nops(w),w)],`+`)=0 then RETURN(true): fi: od: false: end: #Walks with steps with m steps a and n steps -b Walks:=proc(a,b,m,n) local gu,gu1,gu2,i1,i,w: option remember: if n=0 then RETURN({[a$m]}) fi: if m=0 then RETURN({[(-b)$n]}) fi: gu1:=Walks(a,b,m-1,n): gu:={seq([op(gu1[i1]),a],i1=1..nops(gu1))}: gu2:=Walks(a,b,m,n-1): for i from 1 to nops(gu2) do w:=gu2[i]: if not IsBad(w,a) then gu:=gu union {[op(w),-b]}: fi: od: gu: end: #LWwords(a,b,Len1,Sum1): #all the words in {a,-b} of length Len1 that sum to Sum1 and #avoid a factor of the form a[-a](-b) LWwords:=proc(a,b,Len1,Sum1) local gu,gu1,gu2,i1,i,w: option remember: if Len1=0 then if Sum1=0 then RETURN({[]}): else RETURN({}): fi: fi: gu1:=LWwords(a,b,Len1-1,Sum1-a): gu:={seq([op(gu1[i1]),a],i1=1..nops(gu1))}: gu2:=LWwords(a,b,Len1-1,Sum1+b): for i from 1 to nops(gu2) do w:=gu2[i]: if not IsBad(w,a) then gu:=gu union {[op(w),-b]}: fi: od: gu: end: Aab:=proc(a,b,n):LWwords(a,b,(a+b)*n,0);end: #Corpus(a,b,Len,Sum1): #The sequence of LW-words of length (a+b)*i+Sum1 mod (a+b) #for i=0..Len. For example, try #Corpus(3,2,3,0); Corpus:=proc(a,b,Len,Sum1) local Sum1a,i: Sum1a:= Sum1 mod (a+b): [seq(LWwords(a,b,(a+b)*i+Sum1a,Sum1),i=0..Len)]: end: #CHT(S,V):Given a set S of words, and a vertex V=[H,T] #with H and T words, #finds the set of all words in S that #starts with H and #ends with T and returns that set with H and T chopped #For example, try: #CHT(Aab(1,1,5),[[-1],[-1]]); CHT:=proc(S,V) local gu,w,k1,k2,i,H,T: option remember: H:=V[1]: T:=V[2]: k1:=nops(H): k2:=nops(T): gu:={}: for i from 1 to nops(S) do w:=S[i]: if [op(1..k1,w)]=H and [op(nops(w)-k2+1..nops(w),w)]=T then gu:=gu union {[op(k1+1..nops(w)-k2,w)]}: fi: od: gu: end: #Milim(Alph1,Len1,Sum1): all the words of length k in the alphabet Alph1 #that sum to Sum1 Milim:=proc(Alph1,Len1,Sum1) local gu,i,j,ot1,lu: if Len1<0 then RETURN({}): fi: if Len1=0 then if Sum1=0 then RETURN({[]}): else RETURN({}): fi: fi: gu:={}: for i from 1 to nops(Alph1) do ot1:=Alph1[i]: lu:=Milim(Alph1,Len1-1,Sum1-ot1): gu:=gu union {seq([op(lu[j]),ot1],j=1..nops(lu))}: od: gu: end: #PossiblePairs(Alph1,Len1,Sum1): all the possible pairs [V1,V2] in the alphabet Alph1 such #that nops(V1)+nops(V2)=Len1 and Sum(V1)+Sum(V2)=Sum1 PossiblePairs:=proc(Alph1,Len1,Sum1) local gu,i,j: gu:=Milim(Alph1,Len1,Sum1): {seq(seq([[op(1..j,gu[i])],[op(j+1..nops(gu[i]),gu[i])]],j=0..nops(gu[i])),i=1..nops(gu))}: end: #CLONES1(Corp1,V,i): Given a vertex V=[Prefix, Suffix] in an alphabet #and a corpus Corp1, (a sequence of sets of words (in that same alphabet) #of increasing lengths), #finds the set of i-clones, i.e. those vertices V1 such that # CHT(Corp1[nops(Corp1)],V)=CHT(Corp1[nops(Corp1)-i],V1) #For example, try: CLONES1(Corpus(1,1,4,0),[[-1],[1]],1): CLONES1:=proc(Corp1,V,i) local S1,S2,Len,Sum1,Alph,lu,gu,mu,i1: if i>= nops(Corp1) then RETURN({}): fi: S1:=Corp1[nops(Corp1)]: S2:=Corp1[nops(Corp1)-i]: Len:=nops(V[1])+nops(V[2])-(nops(S1[1])-nops(S2[1])): Sum1:=convert(V[1],`+`)+convert(V[2],`+`): Alph:={seq(op(S1[i1]),i1=1..nops(S1))}: lu:=CHT(S1,V): gu:=PossiblePairs(Alph,Len,Sum1): mu:={}: for i1 from 1 to nops(gu) do if CHT(S2,gu[i1])=lu then mu:=mu union {gu[i1]}: fi: od: mu: end: CLONE:=proc(Corp1,V) local i,gu,S: S:=Corp1[nops(Corp1)]: if CHT(S,V)={} then RETURN({}): fi: for i from nops(Corp1) to 1 by -1 do gu:=CLONES1(Corp1,V,i): if gu<>{} then if nops(gu)>1 then print(V, `has more than one clone`): fi: RETURN(gu[1]): fi: od: gu: FAIL: end: #WhichPair(C,a,b,V): Given a corpus C in the alphabet {a,-b} and #a vertex V, decides which pair of sons to make heirs #For example, try: WhichPair(Corpus(1,1,4),1,1,[[],[]]); WhichPair:=proc(C,a,b,V) local lu1,lu2,S,d11,d12,d21,d22,d1,d2: if V<>[[],[]] and CLONE(C,V)<>FAIL then print(V, ` is already a clone , he is not allowed to have children`): RETURN(FAIL): fi: S:=C[nops(C)]: lu1:={[[op(V[1]),a],V[2]],[[op(V[1]),-b],V[2]]}: lu2:={[V[1],[a,op(V[2])]],[V[1],[-b,op(V[2])]]}: lu1,lu2: if CLONE(C,lu1[1])<>FAIL and CLONE(C,lu1[2])<>FAIL then RETURN(lu1): fi: if CLONE(C,lu2[1])<>FAIL and CLONE(C,lu2[2])<>FAIL then RETURN(lu2): fi: if CLONE(C,lu1[1])<>FAIL or CLONE(C,lu1[2])<>FAIL then RETURN(lu1): fi: if CLONE(C,lu2[1])<>FAIL or CLONE(C,lu2[2])<>FAIL then RETURN(lu2): fi: d11:=igcd(nops(CHT(S,lu1[1])),nops(S)): d12:=igcd(nops(CHT(S,lu1[2])),nops(S)): d21:=igcd(nops(CHT(S,lu2[1])),nops(S)): d22:=igcd(nops(CHT(S,lu2[2])),nops(S)): if min(d11,d12)>min(d21,d22) then RETURN(lu1): elif min(d11,d12)=d2 then RETURN(lu1) else RETURN(lu2): fi: fi: end: #IniTree(R): The initial tree with root R IniTree:=proc(R) [{},{},{R},R]: end: #BetterTree(C,a,b,T): Given a Corpus C, of a language in {a,-b} and #a tree T as a five-tuple #[Internals,CommitedLeaves,TempLeaves,Root] #picks one of the temporary leaves and finds its best children #making two new leaves and turing it into an internal vertex #The internal vertices are represented as a pair [vertex, SetOfItsChildren] #For example,try: BetterTree(Corpus(3,2,3,0),3,2,[{},{},{[[],[]]},[[],[]]); BetterTree:=proc(C,a,b,T) local T1,T2,T3,T4,tleaf,gpair,j: T1:=T[1]: T2:=T[2]: T3:=T[3]: T4:=T[4]: if nops(T3)=0 then RETURN([T1,T2,T4]): fi: tleaf:=T3[1]: gpair:=WhichPair(C,a,b,tleaf): T1:=T1 union {[tleaf,gpair]}: T3:=T3 minus {tleaf}: for j from 1 to nops(gpair) do if CLONE(C,gpair[j])<>FAIL then T2:=T2 union {gpair[j]}: else T3:=T3 union {gpair[j]}: fi: od: [T1,T2,T3,T4]: end: #BuildTree(C,a,b): Given a corpus C in the alphabet {a,-b} and a root R #builds a good family tree. For example, try: #BuildTree(Corpus(1,1,4,0),1,1): BuildTree:=proc(C,a,b) local T,i: T:=IniTree([[],[]]): while nops(T)<>3 do T:=BetterTree(C,a,b,T) : od: if {seq(CLONE(C,T[2][i]),i=1..nops(T[2]))} minus {{},seq(T[1][i][1],i=1..nops(T[1]))}<>{} then print(`The tree is not self-contained`): fi: [T[1],{seq([T[2][i],CLONE(C,T[2][i])],i=1..nops(T[2]))}]: end: DiscoverGrammar:=proc(a,b,Len1)local T, i,gu,mu,C,vert: C:=Corpus(a,b,Len1,0): mu:={seq(op(C[i]),i=1..nops(C))}: T:=BuildTree(C,a,b): gu:={}: for i from 1 to nops(T[1]) do vert:=T[1][i][1]: if member([op(vert[1]),op(vert[2])],mu) then gu:=gu union {vert}: fi: od: [T,gu]: end: #GFgrammar(G,x): The weight-enumerator #for the language generated by (linear) `grammar' G #in the variable x GFgrammar:=proc(G,x) local eq,var,z,i,eq1,T: T:=G[1]: var:={seq(z[T[1][i][1]],i=1..nops(T[1])), seq(z[T[2][i][1]],i=1..nops(T[2]))}: eq:={}: for i from 1 to nops(T[1]) do eq1:=z[T[1][i][1]]-z[T[1][i][2][1]]-z[T[1][i][2][2]]: if member(T[1][i][1],G[2]) then eq1:=eq1-x^(nops(T[1][i][1][1])+nops(T[1][i][1][2]) ): fi: eq:=eq union {eq1}: od: for i from 1 to nops(T[2]) do if T[2][i][2]={} then eq1:=z[T[2][i][1]]: else eq1:=z[T[2][i][1]]- z[T[2][i][2]]* x^(nops(T[2][i][1][1])+nops(T[2][i][1][2]) -nops(T[2][i][2][1])-nops(T[2][i][2][2])): fi: eq:=eq union {eq1}: od: subs(solve(eq,var),z[[[],[]]]): end: #IsGarbageZ(w,a,b): given a word w, decides whether it is garbage #because it has a proper zero-factor IsGarbageZ:=proc(w,a,b) local i,j,w1: w1:=subs({seq([i]=i,i=1..b)},w): for i from 1 to nops(w1)-1 do for j from i+1 to nops(w1) do if convert([op(i..j,w1)],`+`)=0 then RETURN(true): fi: od: od: false: end: #IsGarbageM(w,a,b): given a word w, decides whether it is garbage #because it has a mishap IsGarbageM:=proc(w,a,b) local i,j: for i from 1 to nops(w)-1 do for j from i+1 to nops(w) do if w[i]=a and w[j]=-b and convert(subs([1]=1,[op(i..j-1,w)]),`+`)=0 then RETURN(true): fi: od: od: false: end: #IsGarbage(w,a,b): Is it garbage either because of zero-factor or #because of a mishap IsGarbage:=proc(w,a,b):IsGarbageZ(w,a,b) or IsGarbageM(w,a,b):end: #CleanUp(S,a,b): Cleans up a set of words S in {a,-b} CleanUp:=proc(S,a,b) local i,gu,w: gu:={}: for i from 1 to nops(S) do w:=S[i]: if not IsGarbage(w,a,b) then gu:=gu union {w}: fi: od: gu: end: #CF32(A): The Fundamental decomposition of a word #in {3,-2} that sums to A, w/o mishaps or zero-factors. For example, try: #CF32(4); CF32:=proc(A) local mu1,mu2,mu3,mu1m,mu2m,vu,i,j: option remember: if not type(A, integer) then ERROR(`Input of CF32 should be an integer`): fi: if A=0 then RETURN({[[0]]}): fi: if A=1 then RETURN({[[1]]}): fi: if A=-1 then RETURN({[-2,[1]],[[1],-2]} ): fi: if A=-2 then RETURN({ [-2],[[1],-2,-2,[1]]}): fi: if A>1 then mu3:=CF32(A-3): mu2:=CF32(A-2): mu1:=CF32(A-1): mu1m:=CF32(-1): mu2m:=CF32(-2): vu:={seq([3, op(mu3[i])],i=1..nops(mu3))} union {seq(seq([op(mu1m[j]),3, op(mu2[i])],i=1..nops(mu2)),j=1..nops(mu1m))} union {seq(seq([op(mu2m[j]),3, op(mu1[i])],i=1..nops(mu1)),j=1..nops(mu2m))} : vu:=subs([0]=NULL,vu): RETURN(CleanUp(vu,3,2)): fi: if A<-2 then mu2:=CF32(A+2): mu1:=CF32(A+1): vu:={seq([-2, op(mu2[i])],i=1..nops(mu2))} union {seq([[1],-2, op(mu1[i])],i=1..nops(mu1))} : vu:=subs([0]=NULL,vu): RETURN(CleanUp(vu,3,2)): fi: FAIL: end: #Survivors1E32(V): Given a vertex V finds the #fundamental factorizations of [-A] (where A:=Sum(V[1])+Sum(V[2]) #that survive after the first purge (w/o using the #self-referential rule of [1]) Survivors1E32:=proc(V) local A,gu,lu,i: A:=convert(V[1],`+`)+convert(V[2],`+`); gu:=CF32(-A): lu:={}: for i from 1 to nops(gu) do if not IsGarbageM([op(V[1]),op(gu[i]),op(V[2])],3,2) then lu:=lu union {gu[i]}: fi: od: CleanUp(lu,3,2): end: #SR132(): The Self-Referential representation of [1] in terms of #itself (in the {3,-2} language) SR132:=proc() : {[3,-2],[-2,3],[-2,[1],3,[1],-2]}: end: #FattenUp32a(w):Given a word w in {3,-2,[1]}, replaces it by the #triple obtained by replacing the first [1] by SR132() FattenUp32a:=proc(w) local i,j,lu: lu:=SR132(): for i from 1 to nops(w) while w[i]<>[1] do od: if i=nops(w)+1 then RETURN({w}): fi: {seq( [op(1..i-1,w),op(lu[j]),op(i+1..nops(w),w)],j=1..nops(lu))}: end: #FattenUp32(S):Given a set of words S in {3,-2,[1]}, #For each word, replaces it by the #triple obtained by replacing the first [1] by SR132() FattenUp32:=proc(S) local i: {seq(op(FattenUp32a(S[i])),i=1..nops(S))}: end: #SurvivorsE32(V,i): Given a vertex V finds the #survivors after the i-th purge SurvivorsE32:=proc(V,i) local gu,lu,i1,w,j1: if i=0 then RETURN(FAIL): fi: if i=1 then RETURN(Survivors1E32(V)): fi: gu:=SurvivorsE32(V,i-1): for j1 from 1 to nops(gu) do if not member([1],{op(gu[j1])}) then print(gu[j1], `is a permanent survivor`): RETURN(FAIL): fi: od: gu:=FattenUp32(gu): gu:=CleanUp(gu,3,2): lu:={}: for i1 from 1 to nops(gu) do w:=[op(V[1]),op(gu[i1]),op(V[2])]: if not IsGarbageM(w,3,2) then lu:=lu union {gu[i1]}: fi: od: CleanUp(lu,3,2): end: #ProveEmpty32(V,i): Finds out whether the vertex V #in the family-tree of the grammar is #empty after i purgings #For example, try: ProveEmpty32([[],[-2,3,-2,-2,-2,3]],2); ProveEmpty32:=proc(V,i) local gu,i1,Vt: Vt:=[op(V[1]),op(V[2])]: if convert(Vt,`+`)=0 and Mishaps(Vt,3,2)<>{} then RETURN(true): fi: for i1 from 1 to i do gu:=SurvivorsE32(V,i1): if gu={} then RETURN(true): fi: if gu=FAIL then RETURN(false): fi: od: false: end: #ProveGrammar32(G,K): #Tries to rigorously prove that #grammar G=[T,S] is a good grammar, i.e. its Clones are #as stated using K purgings, for example, try: #G:=DiscoverGrammer(3,2,3): ProveGrammar32(G,2); ProveGrammar32:=proc(G,K) local i,T2,leaf,T,S,maxL,shofet: S:=G[2]: S:={seq([op(S[i][1]),op(S[i][2])],i=1..nops(S))}: maxL:=max(seq(nops(S[i]),i=1..nops(S))): if S minus {seq(op(LWwords(3,2,i,0)),i=0..maxL)}<>{} then print(`The set of good Internal vertices does not yield L-W words`): RETURN(false): fi: T:=G[1]: T2:=T[2]: for i from 1 to nops(T2) do leaf:=T2[i]: if leaf[2]={} then if not ProveEmpty32(leaf[1],K) then print(`the leaf `, leaf[1], `does not yield the empty set,`): print(`in `, K, `purgings `): shofet:=FAIL: fi: else if not ProveCloneship32(op(leaf),K) then print(leaf[1], `is not a clone of `, leaf[2] ): print(` in `, K, `purgings `): shofet:=FAIL: fi: fi: od: if shofet=FAIL then FAIL: else true: fi: end: #FattenUp32L(L):Given a List of set of words S in {3,-2,[1]}, #For each entry-set, word, replaces it by the #triple obtained by replacing the first [1] by SR132() #For example, try: FattenUp32L([{[[1]]}]) FattenUp32L:=proc(L) local i: [seq(FattenUp32(L[i]),i=1..nops(L)) ]: end: #SpellOut(ListOfWords,ListOfSets): Given a list of concrete words ListOfWords, #and a list of sets of words, ListOfWords returns the set of all words #of the form ListOfWords[1]ListOfSets[1][i1]ListOfWords[2]ListOfSets[2][i2]... #ListOfWords[nops(ListOfWords)] #For example, try: #SpellOut([[],[]],[{[2]}]); SpellOut:=proc(ListOfWords,ListOfSets) local gu,i,k1,k2: if nops(ListOfWords)<>nops(ListOfSets)+1 then ERROR(`The first list should have one more element than the second argument`): fi: gu:={ListOfWords[1]}: for i from 1 to nops(ListOfSets) do gu:= {seq(seq([op(gu[k1]),op(ListOfSets[i][k2])], k2=1..nops(ListOfSets[i])),k1=1..nops(gu))}: gu:={seq([op(gu[k1]),op(ListOfWords[i+1])],k1=1..nops(gu))}: od: gu: end: #Mishaps(w,a,b): given a word w in {a,-b} finds its set of mishaps #For example, try: Mishaps([1,-1,-1,1],1,1); Mishaps:=proc(w,a,b) local i,j,lu,j1: lu:={}: for i from 1 to nops(w)-1 do for j from i+1 to nops(w) do if w[i]=a and w[j]=-b and convert(subs({seq([j1]=j1,j1=1..b-1)},[op(i..j-1,w)]),`+`)=0 then lu:=lu union {[i,j]}: fi: od: od: lu: end: #WeedOut(SetOfWordLists,ListOfFixedWords,a,b): #Given a set of word-lists (in the #letters a,-b, and the meta-letters [1]. ..[b-1]) and a list #of fixed words (in the alphabet {a,-b}} kicks out those word-lists #for which the word obtained by inserting the words of the word-list between #consecutive members of the ListOfFixedWords contains mishaps #For example, try: #WeedOut({[-1]},[[1],[-1]],1,1) WeedOut:=proc(SetOfWordLists,ListOfFixedWords,a,b) local gu,w,wL,i,j,i2: if {seq(nops(SetOfWordLists[i]),i=1..nops(SetOfWordLists))}<> {nops(ListOfFixedWords)-1} then ERROR(`Bad input`): fi: gu:={}: for i from 1 to nops(SetOfWordLists) do wL:=SetOfWordLists[i]: w:=[]: for j from 1 to nops(ListOfFixedWords)-1 do w:=[op(w), op(ListOfFixedWords[j]),op(wL[j])]: od: w:=[op(w),op(ListOfFixedWords[nops(ListOfFixedWords)])]: if Mishaps(w,a,b)={} and {seq(IsGarbage(wL[i2],3,2),i2=1..nops(wL))}={false} then gu:=gu union {wL}: fi: od: gu: end: #LeftOvers32(SetOfWordLists,ListOfFixedWords,i): The set of left-overs #after i purges LeftOvers32:=proc(SetOfWordLists,ListOfFixedWords,i) local gu,Lw,vu,j,j1: gu:=WeedOut(SetOfWordLists,ListOfFixedWords,3,2): if gu={} then RETURN(gu,1): fi: vu:={}: for j from 1 to nops(gu) do Lw:=gu[j]: if not member([1],{seq(op(Lw[j1]),j1=1..nops(Lw))}) then vu:=vu union {Lw}: fi: od: if vu<>{} then RETURN(vu,0): fi: if i=0 then RETURN(gu,1): fi: gu:=LeftOvers32(SetOfWordLists,ListOfFixedWords,i-1): if gu[2]=0 then RETURN(gu): fi: gu:=gu[1]: if gu={} then RETURN({},1): fi: gu:=FattenUp32aLS(gu): gu:=WeedOut(gu,ListOfFixedWords,3,2): vu:={}: for j from 1 to nops(gu) do Lw:=gu[j]: if not member([1],{seq(op(Lw[j1]),j1=1..nops(Lw))}) then vu:=vu union {Lw}: fi: od: if vu<>{} then RETURN(vu,0): fi: gu,1: end: #FattenUp32aL(Lw):Fattening-up a list of words Lw FattenUp32aL:=proc(Lw) local gu,Lw1,i,j,ku,w,mu: if nops(Lw)=1 then w:=Lw[1]: gu:=FattenUp32a(w): RETURN({seq([gu[i]],i=1..nops(gu))}): fi: Lw1:=[op(1..nops(Lw)-1,Lw)]: gu:=FattenUp32aL(Lw1): w:=Lw[nops(Lw)]: mu:=FattenUp32a(w): ku:={}: for i from 1 to nops(gu) do for j from 1 to nops(mu) do ku:=ku union {[op(gu[i]),mu[j]]}: od: od: ku: end: #FattenUp32aLS(SLw): #Given a set of lists of words, gives the union of the fattened versions FattenUp32aLS:=proc(SLw) local i: {seq(op(FattenUp32aL(SLw[i])),i=1..nops(SLw))}: end: ProveEmpty32New1:=proc(V,i) local A,gu,i1: A:=-(convert(V[1],`+`)+convert(V[2],`+`)): gu:=CF32(A): gu:={seq([gu[i1]],i1=1..nops(gu))}: LeftOvers32(gu,V,i): end: ProveEmpty32New:=proc(V,i) evalb(ProveEmpty32New1(V,i)[1]={}): end: #PotentialMishaps(a,b,Vert): Given a vertex Vert= [P1, S1] #(where P1 and S1 are represented as lists) in the alphabet {a,-b} #prefix P1 and a suffix S1, #returns all the location of pairs [i,j] (where the middle #is also a location) that has an a in P1 or a -b in S1 oe both PotentialMishaps:=proc(a,b,Vert) local gu,i,j,P1,S1,pm,ku: P1:=Vert[1]: S1:=Vert[2]: gu:={}: for i from 1 to nops(P1) do if P1[i]=a then pm:=[i,nops(P1)+1]: gu:=gu union {[pm,ImpliedFactorization(a,b,Vert,pm)]}: fi: od: for j from 1 to nops(S1) do if S1[j]=-b then pm:=[nops(P1)+1,nops(P1)+1+j]: gu:=gu union {[pm,ImpliedFactorization(a,b,Vert,pm)]}: fi: od: for i from 1 to nops(P1) do for j from 1 to nops(S1) do if P1[i]=a and S1[j]=-b then pm:=[i, nops(P1)+1+j]: ku:=ImpliedFactorization(a,b,Vert,pm): if ku<>FAIL then gu:=gu union {[pm,ku]}: fi: fi: od: od: gu: end: #ImpliedFactorization(a,b,Vert,pm): Given a vertex Vert=[P1,S1], where #Given two words in {a,-b} P1 and S1 #and a potential mishap pm=[i,j], say, find the implied factorization #as word in {a,-b} and [A]'s where [A] means a word whose sum is A ImpliedFactorization:=proc(a,b,Vert,pm) local w,A,i,j,Sum1: w:=[op(Vert[1]),0,op(Vert[2])]: Sum1:=convert(w,`+`): i:=pm[1]; j:=pm[2]: if not (w[i]=a or w[i]=0) then ERROR(`Bad input`): fi: if not (w[j]=-b or w[j]=0) then ERROR(`Bad input`): fi: if w[i]=a and w[j]=-b then A:=convert([op(i..j-1,w)],`+`): if A=Sum1 then RETURN(subs([0]=NULL,[[-A]])): else RETURN(FAIL): fi: fi: if w[i]=a then if w[j]<>0 then ERROR(`Bad input`): fi: A:=convert([op(i..j,w)],`+`): RETURN(subs([0]=NULL,[[-A],-b,[A+b-Sum1]])): fi: if w[i]=0 then if w[j]<>-b then ERROR(`Bad input`): fi: A:=convert([op(i..j-1,w)],`+`): RETURN(subs([0]=NULL,[[A-Sum1],a,[-(A+a)]])): fi: FAIL: end: #ProveVertexInclusion32(V1,V2,K): Given two vertices, V1, V2 #in {3,-2} proves that #if V2[1]wV2[2] is good then so is V1[1]wV1[2] is good #or equivalently, #if V1[1]wV1[2] is bad then V2[1]wV2[2] is good #by using K purgings ProveVertexInclusion32:=proc(V1,V2,K) local lu,i,w,w1,w2,w3,i1,i2, ListOfFixedWords,SetOfWordLists,gu1,gu2: if not (type(V1,list) and nops(V1)=2 and type(V1[1],list) and type(V1[2],list) and type(V2,list) and nops(V2)=2 and type(V2[1],list) and type(V2[2],list) and type(K, integer) ) then ERROR(`Bad input`): fi: if Mishaps(V1[1],3,2)<>{} or Mishaps(V1[2],3,2)<>{} then print(V1 , `is already bad itself!, hence no comment!`): RETURN(FAIL): fi: lu:=PotentialMishaps(3,2,V1): for i from 1 to nops(lu) do w:=lu[i][2]: if nops(w)=3 then w1:=w[1]: w2:=w[2]: w3:=w[3]: if not (type(w1,list) and nops(w1)=1 and type(w2,integer) and type(w3,list) and nops(w3)=1) then ERROR(w , `is bad input`): fi: ListOfFixedWords:=[V2[1],[w2],V2[2]]: gu1:=CF32(w1[1]):gu2:=CF32(w3[1]): SetOfWordLists:={seq(seq([gu1[i1],gu2[i2]],i1=1..nops(gu1)),i2=1..nops(gu2))}: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: elif nops(w)=2 and type(w[1],integer) then if not type(w[2],list) and nops(w[2])=1 then ERROR(w , ` is bad input `): fi: w1:=w[1]: w2:=w[2]: ListOfFixedWords:=[[op(V2[1]),w1],V2[2]]: gu2:=CF32(w2[1]): SetOfWordLists:={seq([gu2[i2]],i2=1..nops(gu2)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: elif nops(w)=2 and type(w[1],list) then if not type(w[2],integer) then ERROR(w , ` is bad input `): fi: w1:=w[1]: w2:=w[2]: ListOfFixedWords:=[V2[1],[w2,op(V2[2])] ]: gu1:=CF32(w1[1]): SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: elif nops(w)=1 then if type(w[1],list) then ListOfFixedWords:=V2: gu1:=CF32(w[1][1]): SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: else ListOfFixedWords:=V2: gu1:={w}: SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: fi: fi: od: true: end: #ProveCloneship32(V1,V2,K): #Is Vertex V1 a clone of vertex V2, provable in K purges? ProveCloneship32:=proc(V1,V2,K): ProveVertexInclusion32(V1,V2,K) and ProveVertexInclusion32(V2,V1,K): end: #TestProveEmpty32(L2,Len1,Sum1,K): #tests ProveEmpty32(V,K) for L1, L2, e.g. TestProveEmpty32(3,8,4,2) TestProveEmpty32:=proc(L2,Len1,Sum1,K) local gu,i,gu1,gu2,V,S: gu:=PossiblePairs({3,-2},Len1,Sum1): S:=Aab(3,2,L2): gu1:={}: gu2:={}: for i from 1 to nops(gu) do V:=gu[i]: if CHT(S,V)={} and CHT(Aab(3,2,L2-1),V)={} and not member([op(V[1]), op(V[2])],Aab(3,2,(nops(V[1])+nops(V[2]))/5 )) then gu1:=gu1 union {V}: else gu2:=gu2 union {V}: fi: od: print(`There are`, nops(gu1),`vertices that are empirically empty`): for i from 1 to nops(gu1) do if not ProveEmpty32(gu1[i],K) then print(gu1[i], `seems to be a false negative, but perhaps it is not`): print(` empty after all!`): RETURN(false): fi: od: print(`There are`, nops(gu2),`vertices that are empirically non-empty`): for i from 1 to nops(gu2) do if ProveEmpty32(gu2[i],K) then print(gu2[i], ` is a false positive `): RETURN(false): fi: od: true: end: #EmpiricalClones(a,b,V,m,n): Given a vertex B in the L-W language {a,-b} # finds all the vertices with the same sum and length (a+b)*m longer #that seem to be clones of V using the corpus of words of length<=n(a+b) #followed by the non-clones #For example, try: EmpiricalClones(3,2,[[],[]],1,3); EmpiricalClones:=proc(a,b,V,m,n) local gu1,gu2,Sum1,Len1,i,mu: Len1:=nops(V[1])+nops(V[2])+(a+b)*m: Sum1:=convert(V[1],`+`)+convert(V[2],`+`): mu:=PossibleGoodPairs(a,b,Len1,Sum1): gu1:={}: gu2:={}: for i from 1 to nops(mu) do if CHT(Aab(a,b,n),mu[i])=CHT(Aab(a,b,n-m),V) then gu1:=gu1 union {mu[i]}: else gu2:=gu2 union {mu[i]}: fi: od: gu1,gu2: end: #TestProveCloneship32(V,m,n,K): Tests ProveCloneship32 for all #vertices similar to V, after K prunings #For example, try:TestProveCloneship32([[],[]],1,3,K); TestProveCloneship32:=proc(V,m,n,K) local gu,i,gu1,gu2: gu:=EmpiricalClones(3,2,V,m,n): gu1:=gu[1]: gu2:=gu[2]: print(`There are`, nops(gu1), `vertices that seem to be Clones of`,V): for i from 1 to nops(gu1) do if not ProveCloneship32(gu1[i],V,K) then print(gu1[i], `seems to be a false negative in `, K, ` purges , `): print(` but perhaps it is not a clone after all` ): RETURN(false): fi: od: print(`There are`, nops(gu2), `vertices that are not Clones of`,V): for i from 1 to nops(gu2) do if ProveCloneship32(gu2[i],V,K) then print(gu2[i], `is a false positive in`, K, ` purges `): RETURN(false): fi: od: true: end: #PossibleGoodPairs(a,b,Len1,Sum1): #all the possible pairs [V1,V2] in the alphabet Alph1 such #that nops(V1)+nops(V2)=Len1 and #Sum(V1)+Sum(V2)=Sum1 such that V1 and V2 contain no mishaps #For example, try PossibleGoodPairs(3,-2,10,0); PossibleGoodPairs:=proc(a,b,Len1,Sum1) local lu,gu,i: lu:=PossiblePairs({a,-b},Len1,Sum1): gu:={}: for i from 1 to nops(lu) do if Mishaps(lu[i][1],a,b)={} and Mishaps(lu[i][2],a,b)={} then gu:=gu union {lu[i]}: fi: od: gu: end: DiscoverGrammarVerbose:=proc(a,b,Len1)local T, i,gu,mu,C,vert: C:=Corpus(a,b,Len1,0): mu:={seq(op(C[i]),i=1..nops(C))}: T:=BuildTreeV(C,a,b): gu:={}: print(`Let's look which of the internal vertices, [V1,V2]`): print(` is such that V1V2 belongs to our language`): for i from 1 to nops(T[1]) do vert:=T[1][i][1]: if member([op(vert[1]),op(vert[2])],mu) then gu:=gu union {vert}: print(`Internal vertex`, vert, `has this property`): else print(`Internal vertex`, vert, ` does not have this property`): fi: od: [T,gu]: end: #BetterTreeV(C,a,b,T): Given a Corpus C, of a language in {a,-b} and #a tree T as a five-tuple #[Internals,CommitedLeaves,TempLeaves,Root] #picks one of the temporary leaves and finds its best children #making two new leaves and turing it into an internal vertex #The internal vertices are represented as a pair [vertex, SetOfItsChildren] #For example,try: BetterTree(Corpus(3,2,3,0),3,2,[{},{},{[[],[]]},[[],[]]); BetterTreeV:=proc(C,a,b,T) local T1,T2,T3,T4,tleaf,gpair,j: T1:=T[1]: T2:=T[2]: T3:=T[3]: T4:=T[4]: if nops(T3)=0 then print(`There are no more temporary leaves!, we are done.`): RETURN([T1,T2,T4]): fi: print(`There are still non-empty or non-clone leaves`): tleaf:=T3[1]: print(`Let's pick `, tleaf): gpair:=WhichPairV(C,a,b,tleaf): T1:=T1 union {[tleaf,gpair]}: T3:=T3 minus {tleaf}: print(`Let's examine the new-comers`): for j from 1 to nops(gpair) do if CLONE(C,gpair[j])<>FAIL then print(gpair[j], ` is a clone, so it is a permanent leaf,`): T2:=T2 union {gpair[j]}: else print(gpair[j], ` is not a clone, so it is a new (temporay) leaf,`): print(` eventually to have children (and become an internal vertex)`): T3:=T3 union {gpair[j]}: fi: od: [T1,T2,T3,T4]: end: #BuildTreeV(C,a,b): Given a corpus C in the alphabet {a,-b} and a root R #builds a good family tree. For example, try: #BuildTreeV(Corpus(1,1,4,0),1,1): BuildTreeV:=proc(C,a,b) local T,i: T:=IniTree([[],[]]): print(`We start out with the trivial tree`): print(T): while nops(T)<>3 do T:=BetterTreeV(C,a,b,T) : od: if {seq(CLONE(C,T[2][i]),i=1..nops(T[2]))} minus {{},seq(T[1][i][1],i=1..nops(T[1]))}<>{} then print(`The tree is not self-contained`): fi: [T[1],{seq([T[2][i],CLONE(C,T[2][i])],i=1..nops(T[2]))}]: end: #WhichPairV(C,a,b,V): Given a corpus C in the alphabet {a,-b} and #a vertex V, decides which pair of sons to make heirs #For example, try: WhichPairV(Corpus(1,1,4),1,1,[[],[]]); WhichPairV:=proc(C,a,b,V) local lu1,lu2,S,d11,d12,d21,d22,d1,d2: if V<>[[],[]] and CLONE(C,V)<>FAIL then print(V, ` is already a clone , he is not allowed to have children`): RETURN(FAIL): fi: S:=C[nops(C)]: lu1:={[[op(V[1]),a],V[2]],[[op(V[1]),-b],V[2]]}: lu2:={[V[1],[a,op(V[2])]],[V[1],[-b,op(V[2])]]}: print(` Vertex `, V, `has two pairs of children from his two wives`): print(`From the first wife, he had the pair`, lu1): print(`From the second wife, he had the pair`, lu2): if CLONE(C,lu1[1])<>FAIL and CLONE(C,lu1[2])<>FAIL then print(`Both sons from the first wife are clones, so we pick them`): print(`namley we pick, as children of`, V, ` to be `): print(lu1): RETURN(lu1): fi: if CLONE(C,lu2[1])<>FAIL and CLONE(C,lu2[2])<>FAIL then print(`Both sons from the second wife are clones, so we pick them`): print(`namley we pick, as children of`, V, ` to be ` ): print(lu2): RETURN(lu2): fi: if CLONE(C,lu1[1])<>FAIL or CLONE(C,lu1[2])<>FAIL then print(`One of the sons from the first wife is a clone`): if CLONE(C,lu1[1])<>FAIL then print(`namely `, lu1[1]): else print(`namely `, lu1[2]): fi: print(`so we pick the legal children of`, V, ` to be `): print(lu1): RETURN(lu1): fi: if CLONE(C,lu2[1])<>FAIL or CLONE(C,lu2[2])<>FAIL then print(`One of the sons from the second wife is a clone, so we pick them`): if CLONE(C,lu2[1])<>FAIL then print(`namely `, lu2[1]): else print(`namely `, lu2[2]): fi: print(`so we pick the legal children of`, V, `to be `): print(lu2): RETURN(lu2): fi: d11:=igcd(nops(CHT(S,lu1[1])),nops(S)): d12:=igcd(nops(CHT(S,lu1[2])),nops(S)): d21:=igcd(nops(CHT(S,lu2[1])),nops(S)): d22:=igcd(nops(CHT(S,lu2[2])),nops(S)): print(`Let's examine the cardinalities of these four children`): print(`The cardinalites from the first wife are`): print(nops(CHT(S,lu1[1])),nops(CHT(S,lu1[2]))): print(`and their respective gcd with`, nops(S), ` are `): print(d11,d12): print(): print(`The cardinalites from the second wife are`): print(nops(CHT(S,lu2[1])),nops(CHT(S,lu2[2]))): print(`and their respective gcd with`, nops(S), ` are `): print(d21,d22): if min(d11,d12)>min(d21,d22) then print(`The first wife won!, we pick, as legal heirs`, lu1): RETURN(lu1): elif min(d11,d12)=d2 then print(`The first wife won!, we pick, as legal heirs`, lu1): RETURN(lu1) else print(`The second wife won!, we pick, as legal heirs`, lu2): RETURN(lu2): fi: fi: end: DescribeGrammar:=proc(G) local T,G2,i,v: T:=G[1]: G2:=G[2]: print(`Let's first describe the tree. Of course, its root is [[],[]]`): print(`There are `, nops(T[1]), `internal vertices. Here there are`): print(`followed by their sons`): for i from 1 to nops(T[1]) do v:=T[1][i]: print(`The number-`, i, `internal vertex is`, v[1], `and his sons are`): print(v[2]): od: print(`This concludes the listing of the internal vertices and their sons.`): print(): print(`There are `, nops(T[2]), ` leaves. Here there are, `): print(`each followed by his clone (empty or some internal vertex)`): for i from 1 to nops(T[2]) do v:=T[2][i]: print(`The number-`, i, `leaf is`, v[1], `and he is a clone of`, v[2]): od: print(`This concludes the family-tree part of the grammar`): rint(`Finally, let's describe the so-called initial conditions,`): print(`in other words, those internal vertices [V1,V2] that `): print(`have the property that V1V2 belogs to our language`): print(`There are`, nops(G2), `of these guys, here they are:`): print(G2): print(`This concludes the description of the linear grammar of our language.`): print(`Tam ve-nishlam, sevakh le-el bore olam.`); end: #Survivors1E32v(V): Given a vertex V finds the #fundamental factorizations of [-A] (where A:=Sum(V[1])+Sum(V[2]) #that survive after the first purge (w/o using the #self-referential rule of [1]), Verbose version Survivors1E32v:=proc(V) local A,gu,lu,i,CrucialLemma, w,w1: A:=convert(V[1],`+`)+convert(V[2],`+`); print(`We have to prove that all the words in the alphabet {3,-2}, that sum to 0, of the form`): print([op(V[1]),w,op(V[2])]): print(` are bad (i.e. contain mishaps)`): print(`Since the whole must sum to 0, and the sum of the letters of`, V[1], V[2], ` equals `, A): print(`The word w must have sum `, -A): print(`W.l.o.g. we can restrict attention to words w that are mishap-free and that do not contain`): print(` zero-factors `): gu:=CF32(-A): print(`By `, CrucialLemma[-A], ` each such word must have one of the following conceivable factorizations `): print(`where [1] denots a word that sums up to 1`): print(gu): print(`Let's examine them one at a time `): lu:={}: for i from 1 to nops(gu) do print(`Enclosing `, gu[i], `between `, V, ` we get the meta-word (or ,if there are no [1]'s , plain word) `): w1:=[op(V[1]),op(gu[i]),op(V[2])]: print(w1): if not IsGarbageMv(w1,3,2) then print(`Since this meta-word does not conatain mishaps, it survives the first pruning`): lu:=lu union {gu[i]}: else print(`Since this meta-word DOES conatain a mishap, it gets kicked-out at the first pruning`): fi: od: if lu={} then print(`They were all kicked-out after the first prunings!`): else print(`Here are the surviving meta-words after the first pruning`): print(lu): fi: CleanUp(lu,3,2): end: #SurvivorsE32v(V,i): Given a vertex V finds the #survivors after the i-th purge, verbose version SurvivorsE32v:=proc(V,i) local gu,lu,i1,w,j1: if i=0 then RETURN(FAIL): fi: if i=1 then RETURN(Survivors1E32v(V)): fi: gu:=SurvivorsE32(V,i-1): for j1 from 1 to nops(gu) do if not member([1],{op(gu[j1])}) then print(gu[j1], `is a permanent survivor`): RETURN(FAIL): fi: od: gu:=FattenUp32(gu): gu:=CleanUp(gu,3,2): lu:={}: for i1 from 1 to nops(gu) do w:=[op(V[1]),op(gu[i1]),op(V[2])]: if not IsGarbageM(w,3,2) then lu:=lu union {gu[i1]}: fi: od: CleanUp(lu,3,2): end: #ProveEmpty32v(V,i): Proves verbosely out whether the vertex V #in the family-tree of the grammar is #empty after i purgings #For examplev, try: ProveEmpty32v([[],[-2,3,-2,-2,-2,3]],2); ProveEmpty32v:=proc(V,i) local gu,i1,Vt: Vt:=[op(V[1]),op(V[2])]: if convert(Vt,`+`)=0 and Mishaps(Vt,3,2)<>{} then print(Vt, `belongs to the language and has mishaps`): RETURN(true): fi: gu:=Survivors1E32v(V): if gu={} then print(`Everything disapeared after the first purge!`): RETURN(true): fi: for i1 from 2 to i do print(`Let's perform the `, i1, `-th purge `): gu:=PurgeV(V,gu): if gu={} then RETURN(true): fi: if gu=FAIL then print(`It is definitely not empty`): RETURN(false): fi: od: print(`The following are still left after `, i, ` purges `): false: end: #IsGarbageMv(w,a,b): given a word w, decides whether it is garbage #because it has a mishap IsGarbageMv:=proc(w,a,b) local i,j: for i from 1 to nops(w)-1 do for j from i+1 to nops(w) do if w[i]=a and w[j]=-b and convert(subs([1]=1,[op(i..j-1,w)]),`+`)=0 then print(`The factor from position`, i, ` to position `, j, ` namely ` ,[op(i..j,w)] , ` is a mishap `): RETURN(true): fi: od: od: false: end: #PurgeV(V,S): Given a set of meta-words S #performs one pruning verbosely PurgeV:=proc(V,S) local lu,i1,w,j1,gu: print(`We now have the following meta-words to contend with`): print(S): for j1 from 1 to nops(S) do if not member([1],{op(S[j1])}) then print(S[j1], `is a permanent survivor`): RETURN(FAIL): fi: od: print(`Let's fatten-up each of these meta-words , by replacing the left-most [1] by`): print(SR132()): gu:=FattenUp32(S): print(`We get the following set of meta-words`): print(gu): gu:=CleanUp(gu,3,2): print(`Let's clean them up by discarding all those that contain zero-factors and mishaps`): if gu={} then print(`There is nothing left!, QED`): RETURN(gu): fi: print(`After cleaning up, discarding all meta-words that contain mishaps and zero-factors, `): print(` we still have the set `): print(gu): print(`Let's examine them one by one`): lu:={}: for i1 from 1 to nops(gu) do print(`Let's consider `, gu[i1]. `and enclose it inside `, V, ` getting the word ` ): w:=[op(V[1]),op(gu[i1]),op(V[2])]: print(w): if not IsGarbageMv(w,3,2) then print(`Since this meta-word does NOT contain mishaps, we keep it`): lu:=lu union {gu[i1]}: else print(`Since this word DOES contain mishaps, we kick-it out. `): fi: od: print(`The survivors after this purge are`): print(lu): CleanUp(lu,3,2): end: #ProveEmpty32vv(V,i): Proves very verbosely whether the vertex V #in the family-tree of the grammar is #empty after i purgings #For examplev, try: ProveEmpty32vv([[],[-2,3,-2,-2,-2,3]],2); ProveEmpty32vv:=proc(V,i) local gu,i1,Vt: Vt:=[op(V[1]),op(V[2])]: if convert(Vt,`+`)=0 and Mishaps(Vt,3,2)<>{} then print(Vt, `belongs to the language and has mishaps`): RETURN(true): fi: gu:=Survivors1E32vv(V): if gu={} then print(`Everything disapeared after the first purge!`): RETURN(true): fi: for i1 from 2 to i do print(`Let's perform the `, i1, `-th purge `): gu:=PurgeVv(V,gu): if gu={} then RETURN(true): fi: if gu=FAIL then print(`It is definitely not empty`): RETURN(false): fi: od: print(`The following are still left after `, i, ` purges `): false: end: #Survivors1E32vv(V): Given a vertex V finds the #fundamental factorizations of [-A] (where A:=Sum(V[1])+Sum(V[2]) #that survive after the first purge (w/o using the #self-referential rule of [1]), Verbose version Survivors1E32vv:=proc(V) local A,gu,lu,i,CrucialLemma, w,w1: A:=convert(V[1],`+`)+convert(V[2],`+`); print(`We have to prove that all the words in the alphabet {3,-2}, that sum to 0, of the form`): print([op(V[1]),w,op(V[2])]): print(` are bad (i.e. contain mishaps)`): print(`Since the whole must sum to 0, and the sum of the letters of`, V[1], V[2], ` equals `, A): print(`The word w must have sum `, -A): print(`W.l.o.g. we can restrict attention to words w that are mishap-free and that do not contain`): print(` zero-factors `): gu:=CF32(-A): print(`By `, CrucialLemma[-A], ` each such word must have one of the following conceivable factorizations `): print(`where [1] denots a word that sums up to 1`): print(gu): print(`Let's examine them one at a time `): lu:={}: for i from 1 to nops(gu) do print(`Enclosing `, gu[i], `between `, V, ` we get the meta-word (or ,if there are no [1]'s , plain word) `): w1:=[op(V[1]),op(gu[i]),op(V[2])]: print(w1): if not IsGarbageMv(w1,3,2) then print(`Since this meta-word does not conatain mishaps, it survives the first pruning`): lu:=lu union {gu[i]}: else print(`Since this meta-word DOES conatain a mishap, it gets kicked-out at the first pruning`): fi: od: if lu={} then print(`They were all kicked-out after the first prunings!`): else print(`Here are the surviving meta-words after the first pruning`): print(lu): fi: CleanUpV(lu,3,2): end: #PurgeV(V,S): Given a set of meta-words S #performs one pruning verbosely PurgeVv:=proc(V,S) local lu,i1,w,j1,gu: print(`We now have the following meta-words to contend with`): print(S): for j1 from 1 to nops(S) do if not member([1],{op(S[j1])}) then print(S[j1], `is a permanent survivor`): RETURN(FAIL): fi: od: print(`Let's fatten-up each of these meta-words , by replacing the left-most [1] by`): print(SR132()): gu:=FattenUp32(S): print(`We get the following set of meta-words`): print(gu): gu:=CleanUpV(gu,3,2): print(`Let's clean them up by discarding all those that contain zero-factors and mishaps`): if gu={} then print(`There is nothing left!, QED`): RETURN(gu): fi: print(`After cleaning up, discarding all meta-words that contain mishaps and zero-factors, `): print(` we still have the set `): print(gu): print(`Let's examine them one by one`): lu:={}: for i1 from 1 to nops(gu) do print(`Let's consider `, gu[i1]. `and enclose it inside `, V, ` getting the word ` ): w:=[op(V[1]),op(gu[i1]),op(V[2])]: print(w): if not IsGarbageMv(w,3,2) then print(`Since this meta-word does NOT contain mishaps, we keep it`): lu:=lu union {gu[i1]}: else print(`Since this word DOES contain mishaps, we kick-it out. `): fi: od: print(`The survivors after this purge are`): print(lu): CleanUpV(lu,3,2): end: #IsGarbageZv(w,a,b): given a word w, decides whether it is garbage #because it has a proper zero-factor, Verbose version IsGarbageZv:=proc(w,a,b) local i,j,w1: w1:=subs({seq([i]=i,i=1..b)},w): for i from 1 to nops(w1)-1 do for j from i+1 to nops(w1) do if convert([op(i..j,w1)],`+`)=0 then print(`Regarding meta-word`, w): print(`The factor from position `, i, `to position `, j, ` namely `, [op(i..j,w)] ): print(` is a zero-factor, so we kick-it out `): RETURN(true): fi: od: od: false: end: #IsGarbageMv(w,a,b): given a word w, decides whether it is garbage #because it has a mishap, verbose version IsGarbageMv:=proc(w,a,b) local i,j: for i from 1 to nops(w)-1 do for j from i+1 to nops(w) do if w[i]=a and w[j]=-b and convert(subs([1]=1,[op(i..j-1,w)]),`+`)=0 then print(`Regarding the meta-word `, w, `we have that `): print(`the factor from position`, i, ` to position `, j, `is a mishap, being `, [op(i..j,w)]): RETURN(true): fi: od: od: false: end: #IsGarbageV(w,a,b): Is it garbage either because of zero-factor or, verbose version #because of a mishap IsGarbageV:=proc(w,a,b):IsGarbageZv(w,a,b) or IsGarbageMv(w,a,b):end: #CleanUpV(S,a,b): Cleans up a set of words S in {a,-b}, verbose mode CleanUpV:=proc(S,a,b) local i,gu,w: print(`We are cleaning up set`, S): gu:={}: for i from 1 to nops(S) do w:=S[i]: if not IsGarbageV(w,a,b) then print( w, ` is OK so we retain it `): gu:=gu union {w}: else(w, ` is not OK so we kick it out`): fi: od: print(`We finished cleaninging up the set`, S): print(`and the left-overs are`, gu): gu: end: ############start Verbose cloneship32 #ProveVertexInclusion32v(V1,V2,K): Given two vertices, V1, V2 #in {3,-2} proves that #if V2[1]wV2[2] is good then so is V1[1]wV1[2] is good #or equivalently, #if V1[1]wV1[2] is bad then V2[1]wV2[2] is good #by using K purgings; VERBOS version ProveVertexInclusion32v:=proc(V1,V2,K) local lu,i,w,w1,w2,w3,i1,i2, ListOfFixedWords,SetOfWordLists,gu1,gu2: if not (type(V1,list) and nops(V1)=2 and type(V1[1],list) and type(V1[2],list) and type(V2,list) and nops(V2)=2 and type(V2[1],list) and type(V2[2],list) and type(K, integer) ) then ERROR(`Bad input`): fi: if Mishaps(V1[1],3,2)<>{} or Mishaps(V1[2],3,2)<>{} then print(V1 , `is already bad itself!, hence no comment!`): RETURN(FAIL): fi: lu:=PotentialMishaps(3,2,V1): print(`The potential mishaps are `): print(lu): for i from 1 to nops(lu) do w:=lu[i][2]: print(`examining the `, i, `-th mishap whose potential factorization is `, w): if nops(w)=3 then print(` It has three parts `): w1:=w[1]: w2:=w[2]: w3:=w[3]: if not (type(w1,list) and nops(w1)=1 and type(w2,integer) and type(w3,list) and nops(w3)=1) then ERROR(w , `is bad input`): fi: ListOfFixedWords:=[V2[1],[w2],V2[2]]: print(`The List of Fixed Words is`, ListOfFixedWords): gu1:=CF32(w1[1]):gu2:=CF32(w3[1]): print(`In the first crack, we have to insert all the good words that sum up to `, w1[1]): print(`which according to `, CrucialLemma[w1[1]], ` are `): print(gu1): print(`In the second crack, we have to insert all the good words that sum up to `, w3[1]): print(`which according to `, CrucialLemma[w3[1]], ` are `): print(gu2): SetOfWordLists:={seq(seq([gu1[i1],gu2[i2]],i1=1..nops(gu1)),i2=1..nops(gu2))}: print(` after `, K, `purges there are the following left-over `): print(LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]): if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then print(`Since this is non-empty we failed `): RETURN(false): else print(`Since this is empty, there are no minimal counter-examples coming from this potential mishap`): fi: elif nops(w)=2 and type(w[1],integer) then if not type(w[2],list) and nops(w[2])=1 then ERROR(w , ` is bad input `): fi: print(` It has two parts `): w1:=w[1]: w2:=w[2]: ListOfFixedWords:=[[op(V2[1]),w1],V2[2]]: print(`The List of Fixed Words is`, ListOfFixedWords): gu2:=CF32(w2[1]): print(`In the crack, we have to insert all the good words that sum up to `, w2[1]): print(`which according to `, CrucialLemma[w2[1]], ` are `): print(gu2): SetOfWordLists:={seq([gu2[i2]],i2=1..nops(gu2)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then print(`after `, K, `purges the following are left-over`): print(LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]): RETURN(false): else print(`Since this is empty there are no minimal counterexamples coming from this particular`): print(`potential mishap `): fi: elif nops(w)=2 and type(w[1],list) then if not type(w[2],integer) then ERROR(w , ` is bad input `): fi: print(` It has two parts `): w1:=w[1]: w2:=w[2]: ListOfFixedWords:=[V2[1],[w2,op(V2[2])] ]: gu1:=CF32(w1[1]): print(`The List of Fixed Words is`, ListOfFixedWords): print(`In the crack, we have to insert all the good words that sum up to `, w1[1]): print(`which according to `, CrucialLemma[w1[1]], ` are `): print(gu1): SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then print(`after `, K, `purges the following are left-over`): print(LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]): RETURN(false): else print(`Since this is empty there are no minimal counterexamples coming from this particular`): print(`potential mishap `): fi: elif nops(w)=1 then print(` It has one part `): if type(w[1],list) then ListOfFixedWords:=V2: gu1:=CF32(w[1][1]): SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: else ListOfFixedWords:=V2: gu1:={w}: SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: fi: fi: od: true: end: #ProveCloneship32v(V1,V2,K): #Is Vertex V1 a clone of vertex V2, provable in K purges? Verbose version #Verbose version ProveCloneship32v:=proc(V1,V2,K): ProveVertexInclusion32v(V1,V2,K) and ProveVertexInclusion32v(V2,V1,K): end: ############end Verbose cloneship32 ############start Very Verbose cloneship32 #ProveVertexInclusion32vv(V1,V2,K): Given two vertices, V1, V2 #in {3,-2} proves that #if V2[1]wV2[2] is good then so is V1[1]wV1[2] is good #or equivalently, #if V1[1]wV1[2] is bad then V2[1]wV2[2] is good #by using K purgings; VERY VERBOS version ProveVertexInclusion32vv:=proc(V1,V2,K) local lu,i,w,w1,w2,w3,i1,i2, ListOfFixedWords,SetOfWordLists,gu1,gu2: if not (type(V1,list) and nops(V1)=2 and type(V1[1],list) and type(V1[2],list) and type(V2,list) and nops(V2)=2 and type(V2[1],list) and type(V2[2],list) and type(K, integer) ) then ERROR(`Bad input`): fi: if Mishaps(V1[1],3,2)<>{} or Mishaps(V1[2],3,2)<>{} then print(V1 , `is already bad itself!, hence no comment!`): RETURN(FAIL): fi: lu:=PotentialMishaps(3,2,V1): print(`The potential mishaps are `): print(lu): for i from 1 to nops(lu) do w:=lu[i][2]: print(`examining the `, i, `-th mishap whose potential factorization is `, w): if nops(w)=3 then print(` It has three parts `): w1:=w[1]: w2:=w[2]: w3:=w[3]: if not (type(w1,list) and nops(w1)=1 and type(w2,integer) and type(w3,list) and nops(w3)=1) then ERROR(w , `is bad input`): fi: ListOfFixedWords:=[V2[1],[w2],V2[2]]: print(`The List of Fixed Words is`, ListOfFixedWords): gu1:=CF32(w1[1]):gu2:=CF32(w3[1]): print(`In the first crack, we have to insert all the good words that sum up to `, w1[1]): print(`which according to `, CrucialLemma[w1[1]], ` are `): print(gu1): print(`In the second crack, we have to insert all the good words that sum up to `, w3[1]): print(`which according to `, CrucialLemma[w3[1]], ` are `): print(gu2): SetOfWordLists:={seq(seq([gu1[i1],gu2[i2]],i1=1..nops(gu1)),i2=1..nops(gu2))}: print(` after `, K, `purges there are the following left-over `): print(LeftOvers32v(SetOfWordLists,ListOfFixedWords,K)[1]): if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then print(`Since this is non-empty we failed `): RETURN(false): else print(`Since this is empty, there are no minimal counter-examples coming from this potential mishap`): fi: elif nops(w)=2 and type(w[1],integer) then if not type(w[2],list) and nops(w[2])=1 then ERROR(w , ` is bad input `): fi: print(` It has two parts `): w1:=w[1]: w2:=w[2]: ListOfFixedWords:=[[op(V2[1]),w1],V2[2]]: print(`The List of Fixed Words is`, ListOfFixedWords): gu2:=CF32(w2[1]): print(`In the crack, we have to insert all the good words that sum up to `, w2[1]): print(`which according to `, CrucialLemma[w2[1]], ` are `): print(gu2): SetOfWordLists:={seq([gu2[i2]],i2=1..nops(gu2)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then print(`after `, K, `purges the following are left-over`): print(LeftOvers32v(SetOfWordLists,ListOfFixedWords,K)[1]): RETURN(false): else print(`Since this is empty there are no minimal counterexamples coming from this particular`): print(`potential mishap `): fi: elif nops(w)=2 and type(w[1],list) then if not type(w[2],integer) then ERROR(w , ` is bad input `): fi: print(` It has two parts `): w1:=w[1]: w2:=w[2]: ListOfFixedWords:=[V2[1],[w2,op(V2[2])] ]: gu1:=CF32(w1[1]): print(`The List of Fixed Words is`, ListOfFixedWords): print(`In the crack, we have to insert all the good words that sum up to `, w1[1]): print(`which according to `, CrucialLemma[w1[1]], ` are `): print(gu1): SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then print(`after `, K, `purges the following are left-over`): print(LeftOvers32v(SetOfWordLists,ListOfFixedWords,K)[1]): RETURN(false): else print(`Since this is empty there are no minimal counterexamples coming from this particular`): print(`potential mishap `): fi: elif nops(w)=1 then print(` It has one part `): if type(w[1],list) then ListOfFixedWords:=V2: gu1:=CF32(w[1][1]): SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: else ListOfFixedWords:=V2: gu1:={w}: SetOfWordLists:={seq([gu1[i1]],i1=1..nops(gu1)) }: if LeftOvers32(SetOfWordLists,ListOfFixedWords,K)[1]<>{} then RETURN(false): fi: fi: fi: od: true: end: #ProveCloneship32vv(V1,V2,K): #Is Vertex V1 a clone of vertex V2, provable in K purges? Verbose version #VERY verbose version ProveCloneship32vv:=proc(V1,V2,K): ProveVertexInclusion32vv(V1,V2,K) and ProveVertexInclusion32vv(V2,V1,K): end: #LeftOvers32v(SetOfWordLists,ListOfFixedWords,i): The set of left-overs #after i purges Verbose Version LeftOvers32v:=proc(SetOfWordLists,ListOfFixedWords,i) local gu,Lw,vu,j,j1: gu:=WeedOut(SetOfWordLists,ListOfFixedWords,3,2): if gu={} then RETURN(gu,1): fi: vu:={}: for j from 1 to nops(gu) do Lw:=gu[j]: if not member([1],{seq(op(Lw[j1]),j1=1..nops(Lw))}) then vu:=vu union {Lw}: fi: od: if vu<>{} then RETURN(vu,0): fi: if i=0 then RETURN(gu,1): fi: gu:=LeftOvers32(SetOfWordLists,ListOfFixedWords,i-1): if gu[2]=0 then RETURN(gu): fi: gu:=gu[1]: if gu={} then RETURN({},1): fi: gu:=FattenUp32aLS(gu): gu:=WeedOut(gu,ListOfFixedWords,3,2): vu:={}: for j from 1 to nops(gu) do Lw:=gu[j]: if not member([1],{seq(op(Lw[j1]),j1=1..nops(Lw))}) then vu:=vu union {Lw}: fi: od: if vu<>{} then RETURN(vu,0): fi: gu,1: end: ############end Very Verbose cloneship32 #ProveGrammar32v(G,K): #Tries to rigorously prove that #grammar G=[T,S] is a good grammar, i.e. its Clones are #as stated using K purgings, for example, try: #G:=DiscoverGrammer(3,2,3): ProveGrammar32v(G,3); ProveGrammar32v:=proc(G,K) local i,T2,leaf,T,S,maxL,shofet: S:=G[2]: S:={seq([op(S[i][1]),op(S[i][2])],i=1..nops(S))}: maxL:=max(seq(nops(S[i]),i=1..nops(S))): if S minus {seq(op(LWwords(3,2,i,0)),i=0..maxL)}<>{} then print(`The set of good Internal vertices does not yield L-W words`): RETURN(false): fi: T:=G[1]: T2:=T[2]: for i from 1 to nops(T2) do leaf:=T2[i]: if leaf[2]={} then print(`Lemma Number`, i): print(`The vertex`, leaf[1], ` is empty `): print(`Proof: `): if not ProveEmpty32v(leaf[1],K) then print(`the leaf `, leaf[1], `does not yield the empty set,`): print(`in `, K, `purgings `): shofet:=FAIL: else print(`This concludes the proof of Lemma Number `, i): fi: else print(`Lemma Number`, i): print(`The vertex`, leaf[1], ` is a clone of vertex`, leaf[2]): print(`Proof: `): if not ProveCloneship32v(op(leaf),K) then print(leaf[1], `is not a clone of `, leaf[2] ): print(` in `, K, `purgings `): shofet:=FAIL: else print(`This concludes the proof of Lemma Number `, i): fi: fi: od: if shofet=FAIL then FAIL: else true: fi: end: