chap5.txt

  
  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
  
  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.
  
    Example  
    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
  
  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.
  
    Example  
    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
  
  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.
  
    Example  
    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
  
  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.
  
    Example  
    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>