×

Finite semigroup varieties of the form V*D. (English) Zbl 0561.20042

All semigroups in this review are finite and a ”variety” (or ”pseudovariety”) of semigroups (or monoids) is a family closed under finite direct products and division. Intrinsically of interest, varieties also play an important role, well documented in this article, in the study of recognizable languages. The variety D in the title consists of all ”definite” semigroups: ideal extensions of right zero by nilpotent semigroups; V stands for any variety of monoids and V*D is the semigroup variety generated by subdirect products of monoids in V with semigroups in D. (The apparent lack of duality is illusory, since \(V*D=V*LI\), where LI is the variety of ”generalized definite” semigroups: extensions of rectangular bands by nilpotent semigroups.)
Varieties of this form have appeared before in various places. Their importance is underlined by the author’s proof here that every level in the ”dot-depth” hierarchy of Brzozowski corresponds to such a variety. For example as was already known, corresponding to dot-depth one V is the variety J of \({\mathcal J}\)-trivial monoids. For J*D, R. Knast [RAIRO, Inf. Théor. 17, 321-330 (1983; Zbl 0522.68063)] has solved the ”membership problem” - that of effectively deciding whether a given semigroup belongs to the variety. The author conjectures that in general, if V has soluble membership problem then so does V*D, offering various other special cases as evidence.
Reviewer: P.R.Jones

MSC:

20M07 Varieties and pseudovarieties of semigroups
20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata
20M05 Free semigroups, generators and relations, word problems

Citations:

Zbl 0522.68063
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Brzozowski, J.A.; Knast, R., The dot-depth hierarchy of star-free languages is infinite, J. comput. system sci., 16, 37-55, (1978) · Zbl 0368.68074
[2] Brzozowski, J.A.; Simon, I., Characterizations of locally testable events, Discrete math., 4, 243-271, (1973) · Zbl 0255.94032
[3] Clifford, A.H.; Preston, G.B., ()
[4] Eilenberg, S., ()
[5] Eilenberg, S.; Schützenberger, M.P., On pseudovarieties, Advance in math., 19, 413-418, (1976) · Zbl 0351.20035
[6] Knast, R., Semigroup characterization of dot-depth one languages RAIRO inform. théor., (1984), to appear
[7] Krohm, K.; Rhodes, J.; Tilson, B., (), Chapters 5-9
[8] McNaughton, R., Algebraic decision procedures for local testability, Math. systems theory, 8, 60-76, (1974) · Zbl 0287.02022
[9] McNaughton, R.; Papert, S., Counter-free automata, (1971), MIT Press Cambridge, MA · Zbl 0232.94024
[10] Pin, J.E., Variétés de langages et variétés de semigroupes, () · Zbl 0402.68053
[11] Pin, J.E., Variétés de langages et monoïde de parties, Semigroup forum, 20, 11-47, (1980) · Zbl 0451.20061
[12] Pin, J.E., On the semidirect product of two finite semilattices, (1982), Unpublished manuscript
[13] Schützenberger, M.P., On finite monoids having only trivial subgroups, Information and control, 8, 190-194, (1965) · Zbl 0131.02001
[14] Simon, I., Hierarchies of events of dot-depth one, ()
[15] Simon, I., Piecewise testable events, () · Zbl 0316.68034
[16] Straubing, H., Families of recognizable sets corresponding to certain varieties of finite monoids, J. pure appl. algebra, 15, 305-318, (1979) · Zbl 0414.20056
[17] Straubing, H., Aperiodic morphisms and the concatenation product of recognizable languages, J. pure appl. algebra, 15, 319-327, (1979) · Zbl 0407.20056
[18] Tilson, B., On the complexity of finite semigroups, J. pure appl. algebra, 4, 187-208, (1974) · Zbl 0293.20049
[19] B. Tilson, Chapters 11-12 in [4]. · Zbl 0627.20031
[20] Thérien, D., Classification of regular languages by congruences, ()
[21] Thérien, D., Classification of finite monoids: the language approach, Theoret. comput. sci., 14, 195-208, (1981) · Zbl 0471.20055
[22] Thérien, D., Languages recognized by unions of groups, ()
[23] Thérien, D.; Weiss, A., Graph congruences and wreath products, () · Zbl 0559.20042
[24] Stiffler, P.E., Extensions of the fundamental theorem of finite semigroups, Advances in math, 11, 159-209, (1973)
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.