The loop problem for Rees matrix semigroups. (Q2481325)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The loop problem for Rees matrix semigroups. |
scientific article |
Statements
The loop problem for Rees matrix semigroups. (English)
0 references
9 April 2008
0 references
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.
0 references
Rees matrix semigroups
0 references
loop problem
0 references
completely zero-simple semigroups
0 references
Cayley graphs
0 references
finitely generated semigroups
0 references