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.
Mots-clés : rational language, semilinear set, profinite topology, finite monoid
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/item/ITA_2001__35_5_419_0/
[1] , and, The Design and Analisys of Computer Algorithms. Addison Wesley (1974). | Zbl
[2] , Inevitable graphs: A proof of the type II conjecture and some related decision procedures. Internat. J. Algebra and Comput. 1 (1991) 127-146. | MR | Zbl
[3] , On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica 6 (1986) 1-13. | Zbl
[4] , Transductions and Context-free Languages. Teubner, Stuttgart (1979). | MR | Zbl
[5] and, Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. Electronic Comput. 12 (1963) 67-76. | Zbl
[6] and, Algorithms for the solution of systems of linear Diophantine equations. SIAM J. Comput. 11 (1982) 687-708. | MR | Zbl
[7] , A Course in Computational Algebraic Number Theory. GTM, Springer Verlag (1993). | MR | Zbl
[8] , Abelian pointlikes of a monoid. Semigroup Forum 56 (1998) 339-361. | MR | Zbl
[9] and, Abelian kernels of some monoids of injective partial transformations and an application. Semigroup Forum 61 (2000) 435-452. | MR | Zbl
[10] and, Complexity measures for regular expressions. J. Comput. System Sci. 12 (1976) 134-146. | MR | Zbl
[11] and, Algorithms for computing finite semigroups, edited by F. Cucker and M. Shub. Berlin, Lecture Notes in Comput. Sci. (1997) 112-126. | MR | Zbl
[12] ,, and, Ash's type II theorem, profinite topology and Malcev products: Part I. Internat. J. Algebra and Comput. 1 (1991) 411-436. | Zbl
[13] , and, Factoring polynomials with rational coefficients. Math. Ann. 261 (1982) 515-534. | MR | Zbl
[14] ,, and, Monoid Version 2.0. GAP Package (1997).
[15] ,,, and, Report on the program AMoRE. Tech. Rep. 9507, Christian Albrechts Universität, Kiel (1995).
[16] , Varieties of Formal Languages. Plenum, New-York (1986). | MR | Zbl
[17] , A topological approach to a conjecture of Rhodes. Bull. Austral. Math. Soc. 38 (1988) 421-431. | MR | Zbl
[18] and, A conjecture on the Hall topology for the free group. Bull. London Math. Soc. 23 (1991) 356-362. | MR | Zbl
[19] and, Algorithmic Algebraic Number Theory. Cambridge University Press (1989). | MR | Zbl
[20] and, On the profinite topology on a free group. Bull. London Math. Soc. 25 (1993) 37-43. | MR | Zbl
[21] et al., GAP - Groups, Algorithms, and Programming, Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule. Aachen, Germany, fifth Edition (1995).
[22] , Computation with Finitely Presented Groups. Cambridge University Press (1994). | MR | Zbl
[23] , Finite state automata: A geometric approach. Trans. Amer. Math. Soc. 353 (2001) 3409-3464. | MR | Zbl
[24] , Algorithms for matrix canonical forms, Ph.D. thesis. Department of Computer Science, Swiss Federal Institute of Technology (2000) http://www.scg.uwaterloo.ca/~astorjoh/publications.html
[25] , Type II redux, edited by S.M. Goberstein and P.M. Higgins. Reidel, Dordrecht, Semigroups and their applications (1987) 201-205. | MR | Zbl
[26] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.2. Aachen, St Andrews (1999), http://www-gap.dcs.st-and.ac.uk/~gap
