######################################################################
## TEN: Save this file as  TEN. To use it,                           #
## stay in the                                                       #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read TEN: <Enter>                                 #
## 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 TEN, A Maple package, written by Vince Vatter`):
print(`and Doron Zeilberger`):

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.  7, 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, ProveEmpty32, 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 `):
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]=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]=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]=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)<min(d21,d22) then
  RETURN(lu2):
 else
  d1:=igcd(nops(CHT(S,lu1[1])),nops(CHT(S,lu1[2]))):
  d2:=igcd(nops(CHT(S,lu2[1])),nops(CHT(S,lu2[2]))):

  if d1>=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)<min(d21,d22) then
print(`The second wife won!, we pick, as legal heirs`, lu2):
  RETURN(lu2):
 else
print(`It is still a tie, so now let's take gcd within the pair`):
  d1:=igcd(nops(CHT(S,lu1[1])),nops(CHT(S,lu1[2]))):
  d2:=igcd(nops(CHT(S,lu2[1])),nops(CHT(S,lu2[2]))):
print(`The internal gcd of cardinalities are`, d1,d2):
  if d1>=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: