Counting monoids and rational languages (Q1176625)

Let \(N_{p,n}\) represent the semi-ring obtained by taking the quotient of the semi-ring \(N\) of all natural numbers by the congruence identifying \(u\) and \(v\) if \(u=v\) or \(u\) and \(v\) are both \(\geq p\) and congruent modulo \(p\) (the notation \(Z_{p,n}\) adopted by the author and others lacks justification in its reference to \(Z\)). For a semi-ring \(K\) and a (finite) semigroup \(S\), let \(K\langle S\rangle\) denote the multiplicative semigroup of all polynomials in \(S\) with coefficients in \(K\). In particular, \(N_{1,1}\langle S\rangle\) is naturally identified with the power semigroup \({\mathcal P}(S)\). For a pseudovariety \textbf{V} of semigroups, let \(K\langle {\mathbf V}\rangle\) denote the pseudovariety generated by the semigroups \(K\langle S\rangle\) with \(S\in{\mathbf V}\). The paper begins the study of the operation \(S\mapsto K\langle S\rangle\) and its counterpart for pseudovarieties, both for semigroups and monoids, mainly in the case of the semi-rings \(N_{p,n}\). Following the lines of a paper of \textit{J.- E. Pin} [Can. J. Math. 36, 327-343 (1984; Zbl 0555.20038)] on power monoids, the behaviour of the operation \(S\mapsto N_{p,n}\langle S\rangle\) is studied with respect to preservation of properties of Green's relations. The key technique consists in looking at the support of idempotents in \(K\langle S\rangle\). Many examples are included. In the definition of the mapping \(\Phi\) at the bottom of page 226, \(u\) and \(u'\) should be taken in \(A^*\). The ``proof'' of Proposition IV.2 deals only with a special case.