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.


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.


 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.


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.


gap> LanguageAb(aut); 
[ [ 1, 1 ], [ 0, 0 ] + [ 1, 0 ] Z  ]




generated by GAPDoc2HTML