Strongly locally testable semigroups with commuting idempotents and related languages

Carla Selmi

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 33, Issue: 1, page 47-57
  • ISSN: 0988-3754

Abstract

top
If we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determines an element of S: the product of the letters of the word. S is strongly locally testable if whenever two words over the alphabet S have the same factors of a fixed length k, then the products of the letters of these words are equal. We had previously proved [19] that the syntactic semigroup of a rational language L is strongly locally testable if and only if L is both locally and piecewise testable. We characterize in this paper the variety of strongly locally testable semigroups with commuting idempotents and, using the theory of implicit operations on a variety of semigroups, we derive an elementary combinatorial description of the related variety of languages.

How to cite

top

Selmi, Carla. "Strongly locally testable semigroups with commuting idempotents and related languages." RAIRO - Theoretical Informatics and Applications 33.1 (2010): 47-57. <http://eudml.org/doc/222035>.

@article{Selmi2010,
abstract = { If we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determines an element of S: the product of the letters of the word. S is strongly locally testable if whenever two words over the alphabet S have the same factors of a fixed length k, then the products of the letters of these words are equal. We had previously proved [19] that the syntactic semigroup of a rational language L is strongly locally testable if and only if L is both locally and piecewise testable. We characterize in this paper the variety of strongly locally testable semigroups with commuting idempotents and, using the theory of implicit operations on a variety of semigroups, we derive an elementary combinatorial description of the related variety of languages. },
author = {Selmi, Carla},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {strongly locally testable semigroups with commuting idempotents},
language = {eng},
month = {3},
number = {1},
pages = {47-57},
publisher = {EDP Sciences},
title = {Strongly locally testable semigroups with commuting idempotents and related languages},
url = {http://eudml.org/doc/222035},
volume = {33},
year = {2010},
}

TY - JOUR
AU - Selmi, Carla
TI - Strongly locally testable semigroups with commuting idempotents and related languages
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 1
SP - 47
EP - 57
AB - If we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determines an element of S: the product of the letters of the word. S is strongly locally testable if whenever two words over the alphabet S have the same factors of a fixed length k, then the products of the letters of these words are equal. We had previously proved [19] that the syntactic semigroup of a rational language L is strongly locally testable if and only if L is both locally and piecewise testable. We characterize in this paper the variety of strongly locally testable semigroups with commuting idempotents and, using the theory of implicit operations on a variety of semigroups, we derive an elementary combinatorial description of the related variety of languages.
LA - eng
KW - strongly locally testable semigroups with commuting idempotents
UR - http://eudml.org/doc/222035
ER -

References

top
  1. J. Almeida, Finite Semigroups and Universal Algebra, River Edge. N.J. World Scientific, Singapore (1994).  
  2. J. Almeida, The algebra of implicit operations. Algebra Universalis26 (1989) 16-72.  
  3. J. Almeida, Equations for pseudovarieties, J.-E. Pin Ed., Formal properties of finite automata and applications, Springer, Lecture Notes in Computer Science386 (1989).  
  4. J. Almeida, Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra69 (1990) 205-218.  
  5. J. Almeida, On pseudovarieties, varietes of languages, filters of congruences, pseudoidentities and related topics. Algebra Universalis27 (1990) 333-350.  
  6. J. Almeida and P. Weil, Relatively free profinite monoids: an introduction and examples, J.B. Fountain and V.A.R. Gould Eds., Semigroups, Formal Languages and Groups (to appear) (Da rivedere).  
  7. J. Almeida and P. Weil, Free profinite semigroups over semidirect products, Izv. VUZ Matematika 39 (1995) 3-31; English version, Russian Mathem. (Izv. VUZ.) 39 (1995) 1-28.  
  8. C.J. Ash, T.E. Hall and J.-E. Pin, On the varieties of languages associated with some varieties of finite monoids with commuting idempotents. Inform. and Computation86 (1990) 32-42.  
  9. D. Beauquier and J.-E. Pin, Languages and scanners. Theoret. Comput. Sci.84 (1991) 3-21.  
  10. J.A. Brzozowski and I. Simon, Characterization of locally testable events. Discrete Math.4 (1973) 243-271.  
  11. S. Eilenberg, Automata, languages and machines. Academic Press, New York, Vol. B (1976).  
  12. S. Eilenberg and M.P. Schützenberger, On pseudovarieties. Adv. in Math.19 (1976) 413-418.  
  13. R. McNaughton, Algebraic decision procedures for local testability. Math. Systems Theory8 (1974) 60-76.  
  14. J.-E. Pin, Variétés de Langages Formels, Masson, Paris (1984).  
  15. J.-E. Pin and H. Straubing, Monoids of upper triangular matrices. Colloq. Math. Societatis Janos Bolyai 39 Semigroups, Szeged (1981) 259-272.  
  16. J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis14 (1982) 1-10.  
  17. M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. and Control8 (1965) 190-194.  
  18. C. Selmi, Langages et semigroupes testables. Doctoral thesis, University of Paris VII, Paris (1994).  
  19. C. Selmi, Over Testable Languages. Theoret. Comput. Sci.162 (1996) 157-190.  
  20. I. Simon, Piecewise testable events. Proc. 2nd GI Conf., Springer, Lecture Notes in Computer Science33 (1975) 214-222.  
  21. P. Weil, Implicit operations on pseudovarieties: an introduction, J. Rhodes Ed., World Scientific, Singapore, Semigroups and Monoids and Applications (1991).  
  22. Y. Zalcstein, Locally testable languages. J. Computer and System Sciences6 (1972) 151-167.  
  23. Y. Zalcstein Y., Locally testable semigroups. Semigroup Forum5 (1973) 216-227.  
  24. M. Zeitoun, Opérations implicites et variétés de semigroupes finis. Doctoral thesis, University of Paris VII, Paris (1993).  

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.