[MathJax off]

5 From Automata to Networks

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.

5.1 Functions

5.1-1 IsStarClosed

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> 

5.1-2 Is2StarReplaceable

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 \in Q\) with the first two transitions from \(i\) being \(f(i,1)=1\) and \(f(i,2)=x\), where \(x \in Q\setminus\{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> 

5.1-3 IsStratified

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\setminus \{n+1\},\,\, f: Q \times S \rightarrow Q \) and \(n+1\) is a sink state.

If \(i,j \in Q \setminus \{ n+1 \}\),with \(i < j\), and \(i',j' \in 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> 

5.1-4 IsPossibleGraphAut

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