It is not only important to see how a TPN can be interpreted as a finite state automaton. But also if an arbitrary automaton could represent the language of rank encoded permutations of a TPN. Currently within PatternClass it is only possible to check whether deterministic automata are possible representatives of a TPN.
‣ IsStarClosed( aut ) | ( function ) |
Returns: true if the start and accept states in aut are one and the same state.
This has the consequence that the whole rational expression accepted by aut is always enclosed by the Kleene star.
gap> x:=Automaton("det",4,2,[[3,4,2,4],[2,2,2,4]],[1],[2]); < deterministic automaton on 2 letters with 4 states > gap> IsStarClosed(x); false gap> AutToRatExp(x); (a(aUb)Ub)b* gap> y:=Automaton("det",3,2,[[3,2,1],[2,3,1]],[1],[1]); < deterministic automaton on 2 letters with 3 states > gap> IsStarClosed(y); true gap> AutToRatExp(y); ((ba*bUa)(aUb))* gap>
‣ Is2StarReplaceable( aut ) | ( function ) |
Returns: true if none of the states in the automaton aut, which are not the initial state, have a transition to the initial state labelled with the first letter of the alphabet. It also returns true if there is at least one state i ∈ Q with the first two transitions from i being f(i,1)=1 and f(i,2)=x, where x ∈ Q∖{1} and f(x,1)=1.
gap> x:=Automaton("det",3,2,[[1,2,3],[2,2,3]],[1],[2]); < deterministic automaton on 2 letters with 3 states > gap> Is2StarReplaceable(x); true gap> y:=Automaton("det",4,2,[[4,1,1,2],[1,3,3,2]],[1],[1]); < deterministic automaton on 2 letters with 4 states > gap> Is2StarReplaceable(y); true gap> z:=Automaton("det",4,2,[[4,1,1,2],[1,4,2,2]],[1],[4]); < deterministic automaton on 2 letters with 4 states > gap> Is2StarReplaceable(z); false gap>
‣ IsStratified( aut ) | ( function ) |
Returns: true if aut has a specific "layered" form.
A formal description of the most basic stratified automaton is:
(S,Q,f,q_0,A) with S:={1,...,n}, Q:={1,...,m}, n<m, q_0:=1, A:=Q∖ {n+1}, f: Q × S → Q and n+1 is a sink state.
If i,j ∈ Q ∖ { n+1 },with i < j, and i',j' ∈ S, i=i', j=j' then
f(i,i')=i, f(i,j')=j, f(j,j')=j, f(j,i')=j-1 or n+1.
gap> x:=Automaton("det",4,2,[[1,3,1,4],[2,2,4,4]],[1],[2]); < deterministic automaton on 2 letters with 4 states > gap> IsStratified(x); true gap> y:=Automaton("det",4,2,[[1,3,2,4],[2,4,1,4]],[1],[2]); < deterministic automaton on 2 letters with 4 states > gap> IsStratified(y); false gap>
‣ IsPossibleGraphAut( aut ) | ( function ) |
Returns: true if aut returns true in IsStratified, Is2StarReplaceable and IsStarClosed.
An automaton that fulfils the three functions above has the right form to be an automaton representing rank encoded permutations, which are output from a TPN.
gap> x:=Automaton("det",2,2,[[1,2],[2,2]],[1],[1]); < deterministic automaton on 2 letters with 2 states > gap> IsPossibleGraphAut(x); true gap> y:=Automaton("det",2,2,[[1,2],[1,2]],[1],[1]); < deterministic automaton on 2 letters with 2 states > gap> IsPossibleGraphAut(y); false gap> IsStarClosed(y); true gap> Is2StarReplaceable(y); true gap> IsStratified(y); false gap>
generated by GAPDoc2HTML