Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-19T10:18:19.349Z Has data issue: false hasContentIssue false
  • English
  • Français

Strongly locally testable semigroups with commuting idempotents and related languages

Published online by Cambridge University Press:  15 August 2002

Carla Selmi
Carla Selmi*
Affiliation:
LITP, Université de Paris VII, 2 place Jussieu, 75251 Paris Cedex 05, France, and Université de Rouen, Département d'Informatique, place Émile Blondel, 76128 Mont-Saint-Aignan Cedex, France; [email protected].
Get access

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.

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 33 , Issue 1 , January 1999 , pp. 47 - 57
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Almeida, Finite Semigroups and Universal Algebra, River Edge. N.J. World Scientific, Singapore (1994).
Almeida, J., The algebra of implicit operations. Algebra Universalis 26 (1989) 16-72. CrossRef
J. Almeida, Equations for pseudovarieties, J.-E. Pin Ed., Formal properties of finite automata and applications, Springer, Lecture Notes in Computer Science 386 (1989).
Almeida, J., Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon. J. Pure Appl. Algebra 69 (1990) 205-218. CrossRef
Almeida, J., On pseudovarieties, varietes of languages, filters of congruences, pseudoidentities and related topics. Algebra Universalis 27 (1990) 333-350. CrossRef
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).
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.
Ash, C.J., Hall, T.E. and Pin, J.-E., On the varieties of languages associated with some varieties of finite monoids with commuting idempotents. Inform. and Computation 86 (1990) 32-42. CrossRef
Beauquier, D. and Pin, J.-E., Languages and scanners. Theoret. Comput. Sci. 84 (1991) 3-21. CrossRef
Brzozowski, J.A. and Simon, I., Characterization of locally testable events. Discrete Math. 4 (1973) 243-271. CrossRef
S. Eilenberg, Automata, languages and machines. Academic Press, New York, Vol. B (1976).
Eilenberg, S. and Schützenberger, M.P., On pseudovarieties. Adv. in Math. 19 (1976) 413-418. CrossRef
McNaughton, R., Algebraic decision procedures for local testability. Math. Systems Theory 8 (1974) 60-76. CrossRef
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.
Reiterman, J., The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1-10. CrossRef
Schützenberger, M.P., On finite monoids having only trivial subgroups. Inform. and Control 8 (1965) 190-194. CrossRef
C. Selmi, Langages et semigroupes testables. Doctoral thesis, University of Paris VII, Paris (1994).
Selmi, C., Over Testable Languages. Theoret. Comput. Sci. 162 (1996) 157-190. CrossRef
Simon, I., Piecewise testable events. Proc. 2nd GI Conf., Springer, Lecture Notes in Computer Science 33 (1975) 214-222. CrossRef
P. Weil, Implicit operations on pseudovarieties: an introduction, J. Rhodes Ed., World Scientific, Singapore, Semigroups and Monoids and Applications (1991).
Zalcstein, Y., Locally testable languages. J. Computer and System Sciences 6 (1972) 151-167. CrossRef
Zalcstein Y, Y.., Locally testable semigroups. Semigroup Forum 5 (1973) 216-227. CrossRef
M. Zeitoun, Opérations implicites et variétés de semigroupes finis. Doctoral thesis, University of Paris VII, Paris (1993).