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

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 35, Issue: 5, page 419-435
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topDelgado, Manuel. "Commutative images of rational languages and the Abelian kernel of a monoid." RAIRO - Theoretical Informatics and Applications 35.5 (2010): 419-435. <http://eudml.org/doc/222037>.

@article{Delgado2010,

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.
},

author = {Delgado, Manuel},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Rational language; semilinear set; profinite topology; finite monoid.; algorithms; semilinear expressions; commutative images; rational languages; rational expressions; finite monoids},

language = {eng},

month = {3},

number = {5},

pages = {419-435},

publisher = {EDP Sciences},

title = {Commutative images of rational languages and the Abelian kernel of a monoid},

url = {http://eudml.org/doc/222037},

volume = {35},

year = {2010},

}

TY - JOUR

AU - Delgado, Manuel

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 35

IS - 5

SP - 419

EP - 435

AB -
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.

LA - eng

KW - Rational language; semilinear set; profinite topology; finite monoid.; algorithms; semilinear expressions; commutative images; rational languages; rational expressions; finite monoids

UR - http://eudml.org/doc/222037

ER -

## References

top- A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analisys of Computer Algorithms. Addison Wesley (1974). Zbl0326.68005
- 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. Zbl0722.20039
- L. Babai, On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica6 (1986) 1-13. Zbl0593.68030
- J. Berstel, Transductions and Context-free Languages. Teubner, Stuttgart (1979).
- J. Brzozowski and E. McCluskey, Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. Electronic Comput.12 (1963) 67-76. Zbl0119.12903
- T.J. Chou and G.E. Collins, Algorithms for the solution of systems of linear Diophantine equations. SIAM J. Comput.11 (1982) 687-708. Zbl0498.65022
- H. Cohen, A Course in Computational Algebraic Number Theory. GTM, Springer Verlag (1993). Zbl0786.11071
- M. Delgado, Abelian pointlikes of a monoid. Semigroup Forum56 (1998) 339-361. Zbl0909.20050
- M. Delgado and V.H. Fernandes, Abelian kernels of some monoids of injective partial transformations and an application. Semigroup Forum61 (2000) 435-452. Zbl0966.20030
- A. Ehrenfeucht and P. Zeiger, Complexity measures for regular expressions. J. Comput. System Sci.12 (1976) 134-146. Zbl0329.94024
- 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. Zbl0876.20034
- 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. Zbl0791.20079
- A.K. Lenstra, H.W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients. Math. Ann.261 (1982) 515-534. Zbl0488.12001
- S. Linton, G. Pfeiffer, E. Robertson and N. Ruskuc, Monoid Version 2.0. GAPPackage (1997).
- 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).
- J.-E. Pin, Varieties of Formal Languages. Plenum, New-York (1986).
- J.-E. Pin, A topological approach to a conjecture of Rhodes. Bull. Austral. Math. Soc.38 (1988) 421-431. Zbl0659.20056
- J.-E. Pin and C. Reutenauer, A conjecture on the Hall topology for the free group. Bull. London Math. Soc.23 (1991) 356-362. Zbl0754.20007
- M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory. Cambridge University Press (1989). Zbl0685.12001
- L. Ribes and P.A. Zalesski, On the profinite topology on a free group. Bull. London Math. Soc.25 (1993) 37-43.
- M. Schönert et al., GAP- Groups, Algorithms, and Programming, Lehrstuhl D fur Mathematik, Rheinisch Westfalische Technische Hochschule. Aachen, Germany, fifth Edition (1995).
- C.C. Sims, Computation with Finitely Presented Groups. Cambridge University Press (1994). Zbl0828.20001
- B. Steinberg, Finite state automata: A geometric approach. Trans. Amer. Math. Soc.353 (2001) 3409-3464. Zbl0980.20067
- A. Storjohann, Algorithms for matrix canonical forms, Ph.D. thesis. Department of Computer Science, Swiss Federal Institute of Technology (2000) URIhttp://www.scg.uwaterloo.ca/ astorjoh/publications.html
- B. Tilson, Type II redux, edited by S.M. Goberstein and P.M. Higgins. Reidel, Dordrecht, Semigroups and their applications (1987) 201-205. Zbl0623.20047
- The GAPGroup, GAP- Groups, Algorithms, and Programming, Version 4.2. Aachen, St Andrews (1999), URIhttp://www-gap.dcs.st-and.ac.uk/ gap
- S. Willard, General Topology. Addison Wesley (1970).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.