The loop problem for Rees matrix semigroups. (Q2481325): Difference between revisions

Let \(M\) be a monoid with set of generators \(\sigma\colon X^*\to M\), \(\overline X=\{\overline x\mid x\in X\}\) a set of formal inverses for the generators; \(\widehat X=X\cup\overline X\). The (right) loop automaton \(\widehat\Gamma_\sigma(M)\) is obtained from the (right) Cayley graph \(\Gamma_\sigma(M)\) by adding for each edge with label \(x\) an edge in the opposite direction labeled \(\overline x\); the start and the finite state is the identity of \(M\). The (right) loop problem is the language \(L_\sigma(M)\subseteq\widehat X^*\) recognised by the automaton \(\widehat\Gamma_\sigma(M)\). It is shown that a finitely generated completely zero-simple semigroup has context-free loop problem iff its maximal subgroups are virtually free, i.e., have a free subgroup of finite index.