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

Manuel Delgado

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

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

Abstract

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

How to cite

top

Delgado, Manuel. "Commutative images of rational languages and the abelian kernel of a monoid." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.5 (2001): 419-435. <http://eudml.org/doc/92675>.

@article{Delgado2001,
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 - Informatique Théorique et Applications},
keywords = {rational language; semilinear set; profinite topology; finite monoid; algorithms; semilinear expressions; commutative images; rational languages; rational expressions; finite monoids},
language = {eng},
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/92675},
volume = {35},
year = {2001},
}

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
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/92675
ER -

References

top
  1. [1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analisys of Computer Algorithms. Addison Wesley (1974). Zbl0326.68005
  2. [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. Zbl0722.20039MR1112302
  3. [3] L. Babai, On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6 (1986) 1-13. Zbl0593.68030
  4. [4] J. Berstel, Transductions and Context-free Languages. Teubner, Stuttgart (1979). Zbl0424.68040MR549481
  5. [5] J. Brzozowski and E. McCluskey, Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. Electronic Comput. 12 (1963) 67-76. Zbl0119.12903
  6. [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. Zbl0498.65022MR677662
  7. [7] H. Cohen, A Course in Computational Algebraic Number Theory. GTM, Springer Verlag (1993). Zbl0786.11071MR1228206
  8. [8] M. Delgado, Abelian pointlikes of a monoid. Semigroup Forum 56 (1998) 339-361. Zbl0909.20050MR1611062
  9. [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. Zbl0966.20030MR1832319
  10. [10] A. Ehrenfeucht and P. Zeiger, Complexity measures for regular expressions. J. Comput. System Sci. 12 (1976) 134-146. Zbl0329.94024MR418509
  11. [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. Zbl0876.20034MR1661975
  12. [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. Zbl0791.20079
  13. [13] A.K. Lenstra, H.W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients. Math. Ann. 261 (1982) 515-534. Zbl0488.12001MR682664
  14. [14] S. Linton, G. Pfeiffer, E. Robertson and N. Ruškuc, Monoid Version 2.0. GAP Package (1997). 
  15. [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. [16] J.-E. Pin, Varieties of Formal Languages. Plenum, New-York (1986). Zbl0632.68069MR912694
  17. [17] J.-E. Pin, A topological approach to a conjecture of Rhodes. Bull. Austral. Math. Soc. 38 (1988) 421-431. Zbl0659.20056MR966718
  18. [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. Zbl0754.20007MR1125861
  19. [19] M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory. Cambridge University Press (1989). Zbl0685.12001MR1033013
  20. [20] L. Ribes and P.A. Zalesskiĭ, On the profinite topology on a free group. Bull. London Math. Soc. 25 (1993) 37-43. Zbl0811.20026MR1190361
  21. [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. [22] C.C. Sims, Computation with Finitely Presented Groups. Cambridge University Press (1994). Zbl0828.20001MR1267733
  23. [23] B. Steinberg, Finite state automata: A geometric approach. Trans. Amer. Math. Soc. 353 (2001) 3409-3464. Zbl0980.20067MR1837243
  24. [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. [25] B. Tilson, Type II redux, edited by S.M. Goberstein and P.M. Higgins. Reidel, Dordrecht, Semigroups and their applications (1987) 201-205. Zbl0623.20047MR900660
  26. [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. [27] S. Willard, General Topology. Addison Wesley (1970). Zbl0205.26601MR264581

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.