×

Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon. (English) Zbl 0724.08003

The pseudovariety J of finite \({\mathcal J}\)-trivial semigroups and its relationship to piecewise testable languages have been investigated, in particular, by H. Straubing [Semigroup Forum 19, 107-110 (1980; Zbl 0435.20036)] and I. Simon [Autom. Theor. Form. Lang., 2nd GI Conf., Lect. Notes Comput. Sci. 33, 214-222 (1975; Zbl 0316.68034)]. The present paper is devoted to the topological semigroup of n-ary implicit operations on J; among other things, it is shown that this semigroup is generated by the n component projections together with the \(2^ n-1\) idempotents. This result implies the countability of the completion of the metric space \((A^*,d)\) over a finite alphabet A, where \(d(u,v)=2^{-r}\) for the largest integer r such that \(u,v\in A^*\) have the same subwords of length at most r.
Reviewer: M.Armbrust (Köln)

MSC:

08A40 Operations and polynomials in algebraic structures, primal algebras
20M35 Semigroups in automata theory, linguistics, etc.
22A15 Structure of topological semigroups
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Almeida, J., The algebra of implicit operations, Algebra Universalis, 26, 16-32 (1989) · Zbl 0671.08003
[2] Almeida, J., Residually finite congruences and quasi-regular subsets in uniform algebras, Portugal. Math., 46, 313-328 (1989) · Zbl 0688.08001
[3] Almeida, J., Equations for pseudovarieties, (Pin, J.-E., Formal Properties of finite Automata and Applications. Formal Properties of finite Automata and Applications, Lecture Notes in Computer Science, 386 (1989), Springer: Springer Berlin), 148-164
[4] Almeida, J.; Azevedo, A., Implicit operations on certain classes of semigroups, (Goberstein, S.; Higgins, P., Proceedings 1986 Chico Conference. Proceedings 1986 Chico Conference, Semigroups and their Applications (1987), Reidel: Reidel Dordrecht), 1-11
[5] Almeida, J.; Azevedo, A., The join of the pseudovarieties of \(R\)-trivial and \(L\)-trivial semigroups, J. Pure Appl. Algebra, 60, 129-137 (1989) · Zbl 0687.20054
[6] Azevedo, A., Operaçōes implicitas sobre pseudovariedades de semigrupos e aplicaçōes, (Doctoral dissertation (1989), University of Porto)
[7] Burris, S.; Sankappanavar, H. P., A Course in Universal Algebra (1981), Springer: Springer New York · Zbl 0478.08001
[8] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[9] Pin, J.-E., Varieties of Formal Languages (1986), Plenum: Plenum London · Zbl 0632.68069
[10] Reiterman, J., The Birkhoff Theorem for varieties of finite algebras, Algebra Universalis, 14, 1-10 (1982) · Zbl 0484.08007
[11] Simon, I., Piecewise testable events, (Proc. 2nd GI Conf.. Proc. 2nd GI Conf., Lecture Notes in Computer Science, 33 (1975), Springer: Springer Berlin), 214-222 · Zbl 0316.68034
[12] Straubing, H., On finite \(J\)-trivial monoids, Semigroup Forum, 19, 107-110 (1980) · Zbl 0435.20036
[13] H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon, Technical Report SOCS-85.10, McGill University; H. Straubing and D. Thérien, Partially ordered finite monoids and a theorem of I. Simon, Technical Report SOCS-85.10, McGill University · Zbl 0658.20035
[14] Willard, S., General Topology (1970), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0205.26601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.