Back to Search Start Over

Commutative images of rational languages and the Abelian kernel of a monoid

Authors :
Manuel Delgado
Source :
RAIRO - Theoretical Informatics and Applications. 35:419-435
Publication Year :
2001
Publisher :
EDP Sciences, 2001.

Abstract

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.

Details

ISSN :
1290385X and 09883754
Volume :
35
Database :
OpenAIRE
Journal :
RAIRO - Theoretical Informatics and Applications
Accession number :
edsair.doi...........b96dfb97816d6ffa2017ec2acdcab262
Full Text :
https://doi.org/10.1051/ita:2001100