chap7.txt

  
  7. Computating the commutative image of a rational language
  
  
  7.1 Semilinear Sets
  
  The  commutative  image  of a rational language is a semilinear set. One may
  adapt  the  functions  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  semilinear set given by the
  semilinear  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 and Bbb Z
  respectively.    \index{commutative!language}\index{Abelian!language}    The
  commutative   language  recognized  by  an  automaton  (resp.  GTG)  is  the
  commutative  image  of the language recognized by the automaton (resp. GTG).
  The  Abelian  language recognized by an automaton (resp. GTG) is the closure
  under  the  profinite  topology  of  the  commutative  image of the language
  recognized by the automaton (resp. GTG).
  
  7.1-1  RemoveStateCom
  
  >  RemoveStateCom( gtg ) ___________________________________________function
  
  The  first  state  of  generalized  transition graph gtg is removed. The GTG
  obtained recognizes the same commutative language than the original.
  
  7.1-2  DDAtoGTGCom
  
  >  DDAtoGTGCom( A ) ________________________________________________function
  
  Transforms  a  dense  deterministic  finite  automaton  into  a  finite  GTG
  recognizing the same commutative language.
  
  7.1-3  LangGTGCom
  
  >  LangGTGCom( gtg ) _______________________________________________function
  
  Computes the commutative language recognized by a GTG.
  
  7.1-4  LanguageCom
  
  >  LanguageCom( aut ) ______________________________________________function
  
  Computes  the  commutative  language  recognized  by  a  dense deterministic
  automaton.
  
  ---------------------------  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  ]
  ------------------------------------------------------------------
  
  It  is  obvious that not all possible simplifications have been carried out.
  The  case of Bbb Z-semilinear sets is similar, but some more simplifications
  are done.
  
  7.1-5  RemoveStateAb
  
  >  RemoveStateAb( gtg ) ____________________________________________function
  
  The  first state of generalized transition graph gtg is removed. The Abelian
  language  recognized  by  the  GTG  is  the  same  than the Abelian language
  recognized   by   the   original  GTG.  Several  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.
  
  7.1-6  DDAtoGTGAb
  
  >  DDAtoGTGAb( aut ) _______________________________________________function
  
  Transforms  a  dense  deterministic  finite  automaton  into  a  finite  GTG
  recognizing  the  same Abelian language than the Abelian language recognized
  by the original automaton.
  
  7.1-7  LangGTGAb
  
  >  LangGTGAb( gtg ) ________________________________________________function
  
  Computes  the Abelian language recognized by a GTG. It uses the fact that if
  when  removing  a  state  we  obtain  an  edge  labeled by Bbb Z^n, then the
  resulting language is Bbb Z^n.
  
  7.1-8  LanguageAb
  
  >  LanguageAb( A ) _________________________________________________function
  
  Computes  the  Abelian language recognized by a deterministic automaton. For
  the automaton considered above, we obtain
  
  ---------------------------  Example  ----------------------------
    gap> LanguageAb(aut); 
    [ [ 1, 1 ], [ 0, 0 ] + [ 1, 0 ] Z  ]
  ------------------------------------------------------------------