Commutative images of rational languages and the abelian kernel of a monoid
Delgado, Manuel
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 419-435 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2001-01-01
Classification:  20M35,  68Q99 
@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},
     volume = {35},
     year = {2001},
     pages = {419-435},
     mrnumber = {1908864},
     zbl = {1028.68087},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 419-435. http://gdmltest.u-ga.fr/item/ITA_2001__35_5_419_0/

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analisys of Computer Algorithms. Addison Wesley (1974). | Zbl 0326.68005

[2] C.J. Ash, Inevitable graphs: A proof of the type II conjecture and some related decision procedures. Internat. J. Algebra and Comput. 1 (1991) 127-146. | MR 1112302 | Zbl 0722.20039

[3] L. Babai, On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica 6 (1986) 1-13. | Zbl 0593.68030

[4] J. Berstel, Transductions and Context-free Languages. Teubner, Stuttgart (1979). | MR 549481 | Zbl 0424.68040

[5] J. Brzozowski and E. Mccluskey, Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. Electronic Comput. 12 (1963) 67-76. | Zbl 0119.12903

[6] T.J. Chou and G.E. Collins, Algorithms for the solution of systems of linear Diophantine equations. SIAM J. Comput. 11 (1982) 687-708. | MR 677662 | Zbl 0498.65022

[7] H. Cohen, A Course in Computational Algebraic Number Theory. GTM, Springer Verlag (1993). | MR 1228206 | Zbl 0786.11071

[8] M. Delgado, Abelian pointlikes of a monoid. Semigroup Forum 56 (1998) 339-361. | MR 1611062 | Zbl 0909.20050

[9] M. Delgado and V.H. Fernandes, Abelian kernels of some monoids of injective partial transformations and an application. Semigroup Forum 61 (2000) 435-452. | MR 1832319 | Zbl 0966.20030

[10] A. Ehrenfeucht and P. Zeiger, Complexity measures for regular expressions. J. Comput. System Sci. 12 (1976) 134-146. | MR 418509 | Zbl 0329.94024

[11] V. Froidure and J.-E. Pin, Algorithms for computing finite semigroups, edited by F. Cucker and M. Shub. Berlin, Lecture Notes in Comput. Sci. (1997) 112-126. | MR 1661975 | Zbl 0876.20034

[12] K. Henckell, S. Margolis, J.-E. Pin and J. Rhodes, Ash's type II theorem, profinite topology and Malcev products: Part I. Internat. J. Algebra and Comput. 1 (1991) 411-436. | Zbl 0791.20079

[13] A.K. Lenstra, H.W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients. Math. Ann. 261 (1982) 515-534. | MR 682664 | Zbl 0488.12001

[14] S. Linton, G. Pfeiffer, E. Robertson and N. Ruškuc, Monoid Version 2.0. GAP Package (1997).

[15] O. Matz, A. Miller, A. Pothoff, W. Thomas and E. Valkema, Report on the program AMoRE. Tech. Rep. 9507, Christian Albrechts Universität, Kiel (1995).

[16] J.-E. Pin, Varieties of Formal Languages. Plenum, New-York (1986). | MR 912694 | Zbl 0632.68069

[17] J.-E. Pin, A topological approach to a conjecture of Rhodes. Bull. Austral. Math. Soc. 38 (1988) 421-431. | MR 966718 | Zbl 0659.20056

[18] J.-E. Pin and C. Reutenauer, A conjecture on the Hall topology for the free group. Bull. London Math. Soc. 23 (1991) 356-362. | MR 1125861 | Zbl 0754.20007

[19] M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory. Cambridge University Press (1989). | MR 1033013 | Zbl 0685.12001

[20] L. Ribes and P.A. Zalesskiĭ, On the profinite topology on a free group. Bull. London Math. Soc. 25 (1993) 37-43. | MR 1190361 | Zbl 0811.20026

[21] M. Schönert et al., GAP - Groups, Algorithms, and Programming, Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule. Aachen, Germany, fifth Edition (1995).

[22] C.C. Sims, Computation with Finitely Presented Groups. Cambridge University Press (1994). | MR 1267733 | Zbl 0828.20001

[23] B. Steinberg, Finite state automata: A geometric approach. Trans. Amer. Math. Soc. 353 (2001) 3409-3464. | MR 1837243 | Zbl 0980.20067

[24] A. Storjohann, 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] B. Tilson, Type II redux, edited by S.M. Goberstein and P.M. Higgins. Reidel, Dordrecht, Semigroups and their applications (1987) 201-205. | MR 900660 | Zbl 0623.20047

[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

[27] S. Willard, General Topology. Addison Wesley (1970). | MR 264581 | Zbl 0205.26601