×

Equations on the semidirect product of a finite semilattice by a \(J\)- trivial monoid of height \(k\). (English) Zbl 0833.68073

Summary: Let \({\mathbf J}_k\) denote the \(k\)th level of Simon’s hierarchy of \({\mathcal J}\)-trivial monoids. The 1st level \({\mathbf J}_1\) is the \({\mathbf M}\)-variety of finite semilattice. In this paper, we give a complete sequence of equations for the product \({\mathbf J}_1 * {\mathbf J}_k\) generated by all semidirect products of the form \(M* N\) with \(M\in {\mathbf J}_1\) and \(N\in {\mathbf J}_k\). Results of Almeida imply that this sequence of equations is complete for the product \({\mathbf J}_1^{k+ 1}\) or \({\mathbf J}_1*\cdots* {\mathbf J}_1\) (\(k+ 1\) times) generated by all semidirect products of \(k+ 1\) finite semilattice and that \({\mathbf J}_1* {\mathbf J}_k\) is defined by a finite sequence of equations if and only if \(k= 1\). The equality \({\mathbf J}_1* {\mathbf J}_k= {\mathbf J}^{k+ 1}_1\) implies that a conjecture of Pin concerning tree hierarchies of \({\mathbf M}\)-varieties is false.

MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] 1. J. ALMEIDA, Semidirect Products of Pseudovarieties from the Universal Algebraist’s Point of View, J. of Pure and Applied Algebra, 1989, 60, pp. 113-128. Zbl0687.20053 MR1020712 · Zbl 0687.20053
[2] 2. J. ALMEIDA, Semidirectly Closed Pseudovarieties of Locally Trivial Semigroups, Semigroup Forum, 1990, 40, pp. 315-323. Zbl0711.20032 MR1038009 · Zbl 0711.20032
[3] 3. J. ALMEIDA, On Iterated Semidirect Products of Finite Semilattices, J. of Algebra, 1991, 142, pp. 239-254. Zbl0743.20056 MR1125216 · Zbl 0743.20056
[4] 4. C. J. ASH, Finite Semigroups with Commuting Idempotents, J. of Australian Math. Soc., Ser., A, 1987, 43, pp. 81-90. Zbl0634.20032 MR886805 · Zbl 0634.20032
[5] 5. F. BLANCHET-SADRI, Some Logical Characterizations of the Dot-Depth Hierarchy and Applications, Ph. D. Thesis, McGill University, 1989. MR2685431 · Zbl 0682.03015
[6] 6. F. BLANCHET-SADRI, Games, Equations and the Dot-Depth Hierarchy, Computers and Mathematics with applications, 1989, 18, pp. 809-822. Zbl0682.03015 MR1008808 · Zbl 0682.03015
[7] 7. F. BLANCHET-SADRI, On Dot-Depth Two, R.A.I.R.O. Informatique Théorique et applications, 1990, 24, pp. 521-530. Zbl0718.68046 MR1082913 · Zbl 0718.68046
[8] 8. F. BLANCHET-SADRI, Games, Equations and Dot-Depth Two Monoids, Discrete Applied Mathematics, 1992, 39, pp. 99-111. Zbl0791.20068 MR1184681 · Zbl 0791.20068
[9] 9. F. BLANCHET-SADRI, The Dot-Depth of a Generating Class of Aperiodic Monoids is Computable, J. Foundations Comput Sci., 1992, 3, pp. 419-442. Zbl0776.68087 MR1209555 · Zbl 0776.68087
[10] 10. F. BLANCHET-SADRI, Equations and Dot-Depth One, Semigroup Forum, 1993, 47, pp. 305-317. Zbl0814.20048 MR1235764 · Zbl 0814.20048
[11] 11. F. BLANCHET-SADRI, Equations and Monoid Varieties of Dot-Depth One and Two, Theoretical Comput. Sci., 1994, 123, pp. 239-258. Zbl0801.68105 MR1256200 · Zbl 0801.68105
[12] 12. F. BLANCHET-SADRI, On a Complete Set of Generators for Dot-Depth Two, Discrete Applied Mathematics, 1994, 50, pp. 1-25. Zbl0793.68087 MR1272549 · Zbl 0793.68087
[13] 13. F. BLANCHET-SADRI, Some Logical Characterizations of the Dot-Depth Hierarchy and Applications, J. Comp. Syd. Sci. (à paraître). Zbl0831.68066 · Zbl 0831.68066
[14] 14. J. A. BRZOZOWSKI and I. SIMON, Characterizations of Locally Testable Events, Discrete Mathematics, 1973, 4, pp. 243-271. Zbl0255.94032 MR319404 · Zbl 0255.94032
[15] 15. S. EILENBERG, Automata, Languages and Machines, B, Academic Press, New York, 1976. Zbl0359.94067 MR530383 · Zbl 0359.94067
[16] 16. S. EILENBERG and M. P. SCHÜTZENBERGER, On Pseudovarieties, Advances in Mathematics, 1976, 19, pp. 413-418. Zbl0351.20035 MR401604 · Zbl 0351.20035
[17] 17. C. IRASTORZA, Base Non Finie de Variétés, Lecture Notes in Comput. Sci., Springer Verlag, Berlin, 1985, 182, pp. 180-186. Zbl0572.20041 MR786881 · Zbl 0572.20041
[18] 18. J. KARNOFSKI and J. RHODES, Decidability of Complexity One-Half for Finite Semi-groups, Semigroup Forum, 1982, 24, pp. 55-66. Zbl0503.20028 MR645703 · Zbl 0503.20028
[19] 19. G. LALLEMENT, Semigroups and Combinatorial Applications, Wiley, New York, 1979. Zbl0421.20025 MR530552 · Zbl 0421.20025
[20] 20. J. E. PIN, Variétés de langages formels, Masson, Paris, 1984; Varieties of Formal Languages, North Oxford Academic, London, 1986 and Plenum, NewYork, 1986. Zbl0636.68093 MR752695 · Zbl 0636.68093
[21] Varieties of Formal Languages, North Oxford Academic, London, 1986 and Plenum, NewYork, 1986.
[22] 21. J. E. PIN, Hiérarchies de concaténation, R.A.I.R.O. Informatique Théorique, 1984, 18, pp. 23-46. Zbl0559.68062 MR750449 · Zbl 0559.68062
[23] 22. J. E. PIN, On Semidirect Products of Two Finite Semilattices, Semigroup Forum, 1984, 28, pp. 73-81. Zbl0527.20046 MR729653 · Zbl 0527.20046
[24] 23. I. SIMON, Hierarchies of Events of Dot-Depth One, Ph. D. Thesis, University of Waterloo, 1972. MR2623305
[25] 24. I. SIMON, Piecewise Testable Events, Proc. 2nd GI Conference, Lecture Notes in Comput. Sci., Springer Verlag, Berlin, 1975, 33, pp. 214-222. Zbl0316.68034 MR427498 · Zbl 0316.68034
[26] 25. P. STIFFLER, Extension of the Fundamental Theorem of Finite Semigoups, Advances in Mathematics, 1973, 11, pp. 159-209.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.