Sophie

Sophie

distrib > Mandriva > 2010.0 > i586 > media > contrib-release > by-pkgid > 91213ddcfbe7f54821d42c2d9e091326 > files > 544

gap-system-packages-4.4.12-5mdv2010.0.i586.rpm

  
  E. Commutative image of a rational language
  
  The  commutative  image  of  a rational language is a semilinear set, i.e. a
  finite  union  of  semilinear  sets. One may adapt the function to compute a
  rational  expression for the language recognized by an automaton in order to
  compute  directly  the  commutative  image of the language recognized by the
  automaton.  Further  improvement  leads  to  the  direct  computation of the
  closure  in  Bbb Z^n, for the profinite topology, of that commutative image.
  (See [D01] for the correction of the algorithms.) Recall that (see [D98]) if
  a  linear  set  given  by the linear expression a+b_1Bbb N+ cdots +b_pBbb N,
  then  a+b_1Bbb  Z+  cdots +b_pBbb Z is a Bbb Z-semilinear expression for the
  closure under the profinite topology of the semilinear set given. We use the
  terminology commutative language and Abelian language for subsets of Bbb N^n
  and  Bbb  Z^n  respectively.  The  commutative  language  recognized  by  an
  automaton  is  the  commutative  image  of  the  language  recognized by the
  automaton.  The  Abelian  language recognized by an automaton is the closure
  under  the  profinite  topology  of  the  commutative  image of the language
  recognized by the automaton.
  
  
  E.1 Commutative image
  
  A  semilinear  expression  for  the commutative image of a rational language
  given  through  a  rational  expression  can be computed using the following
  function. The algorithm used is described in [D01].
  
  E.1-1 CommutativeImageOfRatExp
  
  > CommutativeImageOfRatExp( rat ) __________________________________function
  
  rat  is  a  rational expression. A semilinear expression for its commutative
  image is returned.
  
  ---------------------------  Example  ----------------------------
    gap> r5;
    (a(aUb))*
    gap> CommutativeImageOfRatExp(r5); 
    [ [ 0, 0 ], [ 1, 1 ] + [ 1, 1 ] N , [ 2, 0 ] + [ 2, 0 ] N , 
      [ 3, 1 ] + [ 1, 1 ] N  + [ 2, 0 ] N  ]
  ------------------------------------------------------------------
  
  E.1-2 LanguageCom
  
  > LanguageCom( aut ) _______________________________________________function
  > FAtosml( aut ) ___________________________________________________function
  
  Computes  the  commutative  language  recognized  by  the  automaton  A. The
  functions are synonyms.
  
  ---------------------------  Example  ----------------------------
     gap> aut := Automaton("det",5,2,[[1,2,4,2,1],[1,1,1,5,1]],[3],[2,3,4,5]);
          |  1  2  3  4  5 
       -  -  -  -  -  -  - 
       a  |  1  2  4  2  1 
       b  |  1  1  1  5  1 
    Initial state: [ 3 ]
    Accepting states: [ 2, 3, 4, 5 ]
    
    gap> AutomatonToRatExp(aut);
    1UabUa(1Uaa*)
    gap> LanguageCom(aut);
    [ [ 1, 1 ], [ 0, 0 ], [ 1, 0 ], [ 2, 0 ], [ 3, 0 ] + [ 1, 0 ] N  ]
  ------------------------------------------------------------------
  
  The  expression  is  simplified,  but  it  is  obvious that not all possible
  simplifications have been carried out.
  
  
  E.2 Abelian image
  
  A  Bbb  Z-semilinear expression for the profinite closure of the commutative
  image  of  a  rational  language  given through a rational expression can be
  computed  using  the  following function. The algorithm used is described in
  [D01].
  
  E.2-1 AbelianImageOfRatExp
  
  > AbelianImageOfRatExp( rat ) ______________________________________function
  
  rat  is  a  rational  expression.  A  Bbb  Z-semilinear  expression  for the
  profinite closure of the commutative image of rat is returned.
  
  ---------------------------  Example  ----------------------------
    gap> AbelianImageOfRatExp(r5);
    [ [ 0, 0 ] + [ 1, 1 ] Z  + [ 0, 2 ] Z  ]
  ------------------------------------------------------------------
  
  The  case  of  Bbb  Z-semilinear  languages is similar to that of semilinear
  languages,  but  some  more simplifications are done. Computations of normal
  forms  of  matrices  aiming  to determine basis for subgroups of Bbb Z^n are
  made.  These  computations  of  normal forms are carried out using functions
  that are part of \GAP.
  
  E.2-2 LanguageAb
  
  > LanguageAb( A ) __________________________________________________function
  > FAtoclsml( A ) ___________________________________________________function
  
  FAtoclsml  computes an expression for the abelian language recognized by the
  automaton A.
  
  LanguageAb  does  the  same  thing  that FAtoclsml but returns true when the
  expression returned corresponds to Bbb Z^n.
  
  ---------------------------  Example  ----------------------------
    gap> LanguageAb(aut); 
    [ [ 1, 1 ], [ 0, 0 ] + [ 1, 0 ] Z  ]
  ------------------------------------------------------------------