1
$\begingroup$

Pseudovarieties of finite monoids are often studied in conjunction with the class of regular languages they recognize (a monoid $M$ recognizes a language $L \subseteq A^*$ if $L = h^{-1}(h(L))$ for some morphism $h\colon A^* \to M$).

In that context, a natural property of the pseudovariety is to require that it be closed under wreath products; on the language side, this corresponds for the class to be closed under cascading: roughly speaking, the above $L$ cascaded with $L' \subseteq (A \times M)^*$ is the language that contains $w = w_1w_2\cdots w_n \in A^*$ iff $(w_1, h(w_1))(w_2, h(w_1w_2))\cdots(w_n, h(w)) \in L'$.

Question: Is there a name for varieties closed under wreath products? Or for varieties of languages to be closed under cascading?

$\endgroup$
1
$\begingroup$

They were called closed M-varieties by Samuel Eilenberg [1, p.135], but nowadays most authors seem to call them (pseudo)-varieties closed under semidirect product, probably because there are many other closure operators in use: (pseudo)-varieties closed under Mal'cev product, under Schützenberger product, under Rhodes expansions, etc.

[1] S. Eilenberg, Automata, languages, and machines, Vol. B. Pure and Applied Mathematics, Vol. 59. Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. xiii+387 pp.

$\endgroup$
  • $\begingroup$ Great, that definitely makes sense! Merci! $\endgroup$ – Michaël Cadilhac Oct 16 '16 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.