Programs over aperiodic monoids (Q1122664)

A program P over a finite monoid M is a finite sequence of instructions, i.e. of words over the alphabet \(I_ n=[[1,n]]\times M^{\{0,1\}}\) where n is a fixed integer. To each program \(P=\iota_ 1...\iota_ k\in I^*_ n\) is associated a function \(f_ P\) from \(\{0,1\}^ n\) into M. This function is defined by the rule: \[ \forall w=w_ 1...w_ n\in \{0,1\}^ n,\quad f_ P(w)=\prod^{k}_{i=1}f_ i(w_{k(i)}) \] if the i-th instruction is \(\iota_ i=(k(i),f_ i)\) for every i in \([[1,k]]\). A language L in \(\{0,1\}^*\) is then said to be recognizable by M iff for each \(n\in {\mathbb{N}}\), there exists a program \(P(n)\in I^*_ n\) and a subset \(F_ n\subset M\) such that \(L\cap \{0,1\}^ n=f^{-1}_{P(n)}(F_ n)\). It is to be noticed that a language recognizable in the usual sense [cf. \textit{J. E. Pin}, Variétés de langages formels (Masson, Paris, 1984; Zbl 0636.68093)] is also recognizable in the sense of the paper, but the converse is false. The paper presents first a specific aperiodic monoid U which is universal in the following sense: any language L over \(\{0,1\}\) can be recognized by U. Secondly, the author studies different classes of non universal monoids. More precisely, it is shown - modulo some technical precisions - that every monoid M in the semigroup varieties \(R\vee L\), DA or \(J_ 1*G_ q\) cannot recognize the language \(MOD_ p=\{w\in \{0,1\}^*\), \(| w|_ 1\equiv 0 [p]\}\). Finally, the author conjectures that an aperiodic monoid M recognizes \(MOD_ p\) iff U divides M.