# Strongly locally testable semigroups with commuting idempotents and related languages

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topSelmi, 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- J. Almeida, Finite Semigroups and Universal Algebra, River Edge. N.J. World Scientific, Singapore (1994).
- J. Almeida, The algebra of implicit operations. Algebra Universalis26 (1989) 16-72. Zbl0671.08003
- J. Almeida, Equations for pseudovarieties, J.-E. Pin Ed., Formal properties of finite automata and applications, Springer, Lecture Notes in Computer Science386 (1989).
- J. Almeida, Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra69 (1990) 205-218. Zbl0724.08003
- J. Almeida, On pseudovarieties, varietes of languages, filters of congruences, pseudoidentities and related topics. Algebra Universalis27 (1990) 333-350. Zbl0715.08006
- 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). Zbl0877.20038
- 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. Zbl0847.20055
- 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. Zbl0699.68091
- D. Beauquier and J.-E. Pin, Languages and scanners. Theoret. Comput. Sci.84 (1991) 3-21. Zbl0753.68054
- J.A. Brzozowski and I. Simon, Characterization of locally testable events. Discrete Math.4 (1973) 243-271. Zbl0255.94032
- S. Eilenberg, Automata, languages and machines. Academic Press, New York, Vol. B (1976). Zbl0359.94067
- S. Eilenberg and M.P. Schützenberger, On pseudovarieties. Adv. in Math.19 (1976) 413-418. Zbl0351.20035
- R. McNaughton, Algebraic decision procedures for local testability. Math. Systems Theory8 (1974) 60-76. Zbl0287.02022
- J.-E. Pin, Variétés de Langages Formels, Masson, Paris (1984).
- J.-E. Pin and H. Straubing, Monoids of upper triangular matrices. Colloq. Math. Societatis Janos Bolyai 39 Semigroups, Szeged (1981) 259-272. Zbl0635.20028
- J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis14 (1982) 1-10. Zbl0484.08007
- M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. and Control8 (1965) 190-194. Zbl0131.02001
- C. Selmi, Langages et semigroupes testables. Doctoral thesis, University of Paris VII, Paris (1994).
- C. Selmi, Over Testable Languages. Theoret. Comput. Sci.162 (1996) 157-190. Zbl0872.68092
- I. Simon, Piecewise testable events. Proc. 2nd GI Conf., Springer, Lecture Notes in Computer Science33 (1975) 214-222. Zbl0316.68034
- P. Weil, Implicit operations on pseudovarieties: an introduction, J. Rhodes Ed., World Scientific, Singapore, Semigroups and Monoids and Applications (1991). Zbl0799.20051
- Y. Zalcstein, Locally testable languages. J. Computer and System Sciences6 (1972) 151-167. Zbl0242.68038
- Y. Zalcstein Y., Locally testable semigroups. Semigroup Forum5 (1973) 216-227. Zbl0273.20049
- M. Zeitoun, Opérations implicites et variétés de semigroupes finis. Doctoral thesis, University of Paris VII, Paris (1993).