Voir la notice de l'article provenant de la source Numdam
Natural algorithms to compute rational expressions for recognizable languages, even those which work well in practice, may produce very long expressions. So, aiming towards the computation of the commutative image of a recognizable language, one should avoid passing through an expression produced this way. We modify here one of those algorithms in order to compute directly a semilinear expression for the commutative image of a recognizable language. We also give a second modification of the algorithm which allows the direct computation of the closure in the profinite topology of the commutative image. As an application, we give a modification of an algorithm for computing the abelian kernel of a finite monoid obtained by the author in 1998 which is much more efficient in practice.
@article{ITA_2001__35_5_419_0,
author = {Delgado, Manuel},
title = {Commutative images of rational languages and the abelian kernel of a monoid},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {419--435},
publisher = {EDP-Sciences},
volume = {35},
number = {5},
year = {2001},
mrnumber = {1908864},
zbl = {1028.68087},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ITA_2001__35_5_419_0/}
}
TY - JOUR AU - Delgado, Manuel TI - Commutative images of rational languages and the abelian kernel of a monoid JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2001 SP - 419 EP - 435 VL - 35 IS - 5 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/item/ITA_2001__35_5_419_0/ LA - en ID - ITA_2001__35_5_419_0 ER -
%0 Journal Article %A Delgado, Manuel %T Commutative images of rational languages and the abelian kernel of a monoid %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2001 %P 419-435 %V 35 %N 5 %I EDP-Sciences %U http://geodesic.mathdoc.fr/item/ITA_2001__35_5_419_0/ %G en %F ITA_2001__35_5_419_0
Delgado, Manuel. Commutative images of rational languages and the abelian kernel of a monoid. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 5, pp. 419-435. http://geodesic.mathdoc.fr/item/ITA_2001__35_5_419_0/