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).
> RemoveStateCom( gtg ) | ( function ) |
The first state of generalized transition graph gtg is removed. The GTG obtained recognizes the same commutative language than the original.
> DDAtoGTGCom( A ) | ( function ) |
Transforms a dense deterministic finite automaton into a finite GTG recognizing the same commutative language.
> LangGTGCom( gtg ) | ( function ) |
Computes the commutative language recognized by a GTG.
> LanguageCom( aut ) | ( function ) |
Computes the commutative language recognized by a dense deterministic automaton.
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.
> 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.
> 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.
> 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.
> LanguageAb( A ) | ( function ) |
Computes the Abelian language recognized by a deterministic automaton. For the automaton considered above, we obtain
gap> LanguageAb(aut); [ [ 1, 1 ], [ 0, 0 ] + [ 1, 0 ] Z ] |
generated by GAPDoc2HTML