Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
| Download
GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
Project: cocalc-sagemath-dev-slelievre
Views: 418346############################################################################# ## This program is free software: you can redistribute it and/or modify ## it under the terms of the GNU General Public License as published by ## the Free Software Foundation, either version 2 of the License, or ## (at your option) any later version. ## ## This program is distributed in the hope that it will be useful, ## but WITHOUT ANY WARRANTY; without even the implied warranty of ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ## GNU General Public License for more details. ## #W classAndBasis.gi Michael Albert, #W Steve Linton, #W Ruth Hoffmann ## ## #Y Copyright (C) 2004-2015 School of Computer Science, #Y University of St. Andrews, North Haugh, #Y St. Andrews, Fife KY16 9SS, Scotland ## ############################################################################# ## #F BoundedClassAutomaton(k) ## ## Returns an automaton, that accepts all rank encoded permutations with ## highest letter being k. ## if not IsBound(MakeWriteOnceAtomic) then BindGlobal("MakeWriteOnceAtomic", ID_FUNC); fi; BOUNDED_CLASS_AUTOMATA_CACHE := MakeWriteOnceAtomic([]); InstallMethod(FlushCaches, [],function() BOUNDED_CLASS_AUTOMATA_CACHE := MakeWriteOnceAtomic([]); TryNextMethod(); end); InstallGlobalFunction(BoundedClassAutomaton, function(k) local states, alphabet, trans, i, j; if not IsBound(BOUNDED_CLASS_AUTOMATA_CACHE[k]) then states := k; alphabet := k; trans := []; for i in [1..k] do trans[i] := []; for j in [1..i] do Add(trans[i],i); od; for j in [(i+1)..k] do Add(trans[i],j-1); od; od; BOUNDED_CLASS_AUTOMATA_CACHE[k] := Automaton("det", states, alphabet, trans, [1], [1]); fi; return BOUNDED_CLASS_AUTOMATA_CACHE[k]; end ); ############################################################################# ## #F BasisAutomaton(a) ## ## Returns an automaton that accepts all permutations of the basis of the ## input autmaton, in rank encoding. ## InstallGlobalFunction(BasisAutomaton, function(a) local a2, b, b2, k, c, c2, d, e, f, t, u, g, g2, h, i, j, l, n; if IsEpsilonAutomaton(a) then a2 := EpsilonCompactedAut(a); b := EpsilonToNFA(a2); b2 := ReducedNFA(b); elif IsNonDeterministicAutomaton(a) then b2 := ReducedNFA(a); else b2 := a; fi; k := b2!.alphabet; c := ReversedAutomaton(b2); c2 := ReducedNFA(c); d := NFAtoDFA(c2); e := MinimalAutomaton(d); f := ComplementDA(e); t := DeletionTransducer(k); u := TransposedTransducer(t); g := CombineAutTransducer(f,u); g2 := ReducedNFA(g); h := NFAtoDFA(g2); i := MinimalAutomaton(h); j := ComplementDA(i); # l := IntersectionAutomaton(j,f); l := NDIntersectionAutomaton(j,f); Info(InfoAutomataSL,1,"Intersected with Language complement ", l!.states," states"); n := MinimalAutomaton(l); # return MinimalAutomaton(NFAtoDFA(ReversedAutomaton(n))); return ReversedAutomaton(n); end ); ###### ## ## This function has been improved with the one below, as there were issues if ## the alphabet exceeded length 9. ## ############################################################################# ## #F SequencesToRatExp(list) ## ## Returns a rational expression that describes all the words in list. ## #InstallGlobalFunction(SequencesToRatExp, function(list) # local k, alph, l; # # k := Maximum(Flat(list)); # alph := JoinStringsWithSeparator(List([1..k], String),""); # l := List(list, x -> JoinStringsWithSeparator(List(x,String),"")); # # return RationalExpression(JoinStringsWithSeparator(l, "U"),alph); #end ); ############################################################################# ## #F SequencesToRatExp(arg) ## ## Returns a rational expression that describes all the words in list. ## Compared to the original function this should work if the alphabet has ## more than 9 letters. ## InstallGlobalFunction(SequencesToRatExp, function(arg) local list,k,ra,p,tmp,i; list:=arg[1]; if IsBound(arg[2]) then k := arg[2]; else k := Maximum(Flat(list)); fi; ra:=[]; for p in list do tmp:=RationalExpression("",k); for i in p do tmp:=ProductRatExp(tmp,RatExpOnnLetters(k,[],[i])); od; #UnionRatExp(ra,tmp); Add(ra,tmp); od; #if Length(arg) = 2 then # k:=arg[2]; #fi; return RationalExpression(JoinStringsWithSeparator(ra, "U"),k); end ); ############################################################################# ## #F ClassAutomaton(a) ## ## Returns an automaton accepting the rank encoded permutations of the ## pattern class described by the input automaton that represents the basis. ## InstallGlobalFunction(ClassAutomaton, function(a) local a2, b, k, b2, c, c2, d, e, f, t, u, g, g2, h, i, j, jj, jjj, l, m, n; if IsEpsilonAutomaton(a) then a2 := EpsilonCompactedAut(a); b := EpsilonToNFA(a2); else b := a; fi; k := b!.alphabet; if IsNonDeterministicAutomaton(b) then b2 := ReducedNFA(b); else b2 := b; fi; c := ReversedAutomaton(b2); c2 := ReducedNFA(c); d := NFAtoDFA(c2); e := MinimalAutomaton(d); f := e; t := InvolvementTransducer(k); u := TransposedTransducer(t); g := CombineAutTransducer(f,u); g2 := ReducedNFA(g); h := NFAtoDFA(g2); i := MinimalAutomaton(h); j := ComplementDA(i); jj := ReversedAutomaton(j); jjj := MinimalAutomaton(jj); l := BoundedClassAutomaton(k); # m := IntersectionAutomaton(jjj,l); m := NDIntersectionAutomaton(jjj,l); # n := MinimalAutomaton(m); n := EpsilonToNFA(m); return n; end ); ############################################################################# ## #F ClassAutFromBaseEncoding(base,k) ## ## Returns an automaton accepting the rank encoded permutations of the ## pattern class described by the basis (in rank encoding) and the highest ## letter k in the rank encoding. ## InstallGlobalFunction(ClassAutFromBaseEncoding, function(base,k) local r, b, c, d, e, f; r := SequencesToRatExp(base); b := RatExpToAut(r); c := ExpandAlphabet(b,k); d := ClassAutomaton(c); e := ReversedAutomaton(d); f := NFAtoDFA(e); return MinimalAutomaton(ReversedAutomaton(f)); end ); ############################################################################# ## #F ClassAutFromBase(perms,k) ## ## Returns an automaton accepting the rank encoded permutations of the ## pattern class described by the basis and the highest letter k in the ## rank encoding. ## InstallGlobalFunction(ClassAutFromBase, function(perms,k) return ClassAutFromBaseEncoding(List(perms, RankEncoding),k); end ); ############################################################################# ## #F RankDecoding(e) ## ## Returns the decoded permutation. ## InstallGlobalFunction(RankDecoding, function(e) local source, result, x; source := [1..Length(e)]; result := []; for x in e do Add(result, source[x]); RemoveSet(source, source[x]); od; return result; end ); ############################################################################# ## #F RankEncoding(p) ## ## Returns a sequence that represents the rank encoding of the input ## permutation. ## InstallGlobalFunction(RankEncoding, function(p) local source, result, x; source := [1..Length(p)]; result := []; for x in p do Add(result, Position(source,x)); RemoveSet(source,x); od; return result; end ); ############################################################################# ## #F ExpandAlphabet(a,newAlphabet) ## ## Returns the input automaton over n letters, where n=newAlphabet. ## InstallGlobalFunction(ExpandAlphabet, function(a,newAlphabet) local trans, eps, k; trans := ShallowCopy(a!.transitions); if IsEpsilonAutomaton(a) then eps := trans[a!.alphabet]; for k in [a!.alphabet..newAlphabet] do Add(trans, []); od; Add(trans, eps); else for k in [a!.alphabet+1..newAlphabet] do Add(trans, []); od; fi; return Automaton(a!.type, a!.states, Length(trans), trans, a!.initial, a!.accepting); end );