1################################################################################ 2## This program is free software: you can redistribute it and/or modify 3## it under the terms of the GNU General Public License as published by 4## the Free Software Foundation, either version 2 of the License, or 5## (at your option) any later version. 6## 7## This program is distributed in the hope that it will be useful, 8## but WITHOUT ANY WARRANTY; without even the implied warranty of 9## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10## GNU General Public License for more details. 11## 12#W inversion.gi Ruth Hoffmann 13## 14## 15#Y Copyright (C) 2004-2015 School of Computer Science, 16#Y University of St. Andrews, North Haugh, 17#Y St. Andrews, Fife KY16 9SS, Scotland 18## 19 20################################################################################ 21## 22#F InversionAut(k) 23## 24## InversionAut builds the automaton that accepts all permutations under the 25## rank encoding with exactly k inversions. 26## 27## 28InstallGlobalFunction(InversionAut,function(k) 29local siz,alph,strt,acc,trans,temp,i,aut; 30 31siz:=k+3; 32alph:=k+1; 33strt:=[1]; 34acc:=[k+2]; 35 36trans:=[]; 37temp:=[1..k]; 38Append(temp,ListWithIdenticalEntries(2,k+2)); 39Add(temp,siz); 40Add(trans,temp); 41for i in [2..alph] do 42 temp:=[i..k+1]; 43 Append(temp,ListWithIdenticalEntries(i+1,siz)); 44 Add(trans,temp); 45od; 46 47aut:=Automaton("det",siz,alph,trans,strt,acc); 48 49return MinimalAutomaton(IntersectionAutomaton(aut,BoundedClassAutomaton(k+1))); 50 51end ); 52 53################################################################################ 54## 55#F InversionAutOfClass(aut,inv) 56## 57## InvserionAutOfClass returns the automaton that accepts all permutations under 58## the rank encoding, lying in the regular class aut, that have exactly inv 59## inversions. 60## 61InstallGlobalFunction(InversionAutOfClass,function(a,inv) 62local iaut,aaut; 63 64iaut:=InversionAut(inv); 65 66if AlphabetOfAutomaton(a) < AlphabetOfAutomaton(iaut) then 67 aaut:=ExpandAlphabet(a,AlphabetOfAutomaton(iaut)); 68elif AlphabetOfAutomaton(a) > AlphabetOfAutomaton(iaut) then 69 iaut:=ExpandAlphabet(iaut,AlphabetOfAutomaton(a)); 70else 71 aaut:=a; 72fi; 73 74return IntersectionAutomaton(iaut,aaut); 75 76end ); 77 78################################################################################ 79## 80#F LoopFreeAut(aut) 81## 82## LoopFreeAut returns the subautomaton of aut that contains no loops of the 83## form (i,i,x) where i is a state and x is any letter in the alphabet. 84## 85InstallGlobalFunction(LoopFreeAut,function(a) 86local trans,j,i; 87 88trans:=List(a!.transitions, ShallowCopy); 89 90for j in [1..Length(trans[1])] do 91 for i in [1..Length(trans)] do 92 Add(trans[i],a!.states+1); 93 if trans[i][j]=j then 94 trans[i][j]:=a!.states+1; 95 fi; 96 od; 97od; 98 99 100return Automaton("det",a!.states+1,a!.alphabet,trans,a!.initial,a!.accepting); 101 102end ); 103 104################################################################################ 105## 106#F LoopVertexFreeAut(aut) 107## 108## LoopVertexFreeAut builds the subautomaton of aut that does not contain the 109## vertices and their transitions in aut that loop to themselves. 110## 111InstallGlobalFunction(LoopVertexFreeAut,function(a) 112local acc,ll,trans,i,j,x,sink; 113 114acc:=FinalStatesOfAutomaton(a); 115ll:=[]; 116trans:=List(a!.transitions, ShallowCopy); 117sink:=a!.states+1; 118 119for i in [1..Length(trans)] do 120 for j in [1..Length(trans[i])] do 121 if trans[i][j]=j then 122 Add(ll,j); 123 fi; 124 Add(trans[i],sink); 125 od; 126od; 127 128for x in [1..a!.states] do 129 if x in ll then 130 for i in [1..Length(trans)] do 131 Unbind(trans[i][x]); 132 od; 133 else 134 for i in [1..Length(trans)] do 135 if trans[i][x] in ll then 136 trans[i][x]:=sink; 137 fi; 138 od; 139 fi; 140od; 141 142return MinimalAutomaton(Automaton("nondet",a!.states+1,a!.alphabet,trans,a!.initial,a!.accepting)); 143 144end ); 145