On the hyperdecidability of semidirect products of pseudovarieties (Q4224014)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1236627
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the hyperdecidability of semidirect products of pseudovarieties |
scientific article; zbMATH DE number 1236627 |
Statements
On the hyperdecidability of semidirect products of pseudovarieties (English)
0 references
30 March 1999
0 references
decidability
0 references
membership problem
0 references
semidirect products
0 references
pseudovarieties of bands
0 references
pseudovarieties of finite groups
0 references
hyperdecidable pseudovarieties
0 references
order-computable pseudovarieties
0 references
hyperdecidability
0 references
pseudovarieties of finite completely simple semigroups
0 references
0 references
0.85522175
0 references
0.8408871
0 references
0.80499727
0 references
0.77786136
0 references
0 references
0.7631204
0 references
0 references
Given a pseudovariety \(\mathcal V\) of (finite) semigroups, the natural decidability question is that of membership in \(\mathcal V\). However, it has become clear that this property is not inherited by some common varietal operations such as semidirect products. Various stronger properties range up to ``order-computability'' (satisfied by the pseudovariety of bands, for instance) and, even stronger, finite generation. The first author introduced the important notion of ``hyperdecidability'', which has a somewhat technical definition in terms of the decidability of the labelling of certain graphs. \textit{C. J. Ash}'s proof of the ``Rhodes conjecture'' [Int. J. Algebra Comput. 1, No. 1, 127-146 (1991; Zbl 0722.20039)] included a proof that the pseudovariety of finite groups is hyperdecidable (without using that term). The authors' main result in this paper is that the semidirect product of a hyperdecidable pseudovariety with an order-computable pseudovariety is again hyperdecidable. Although it is not known whether hyperdecidability is preserved by arbitrary semidirect products, this result has a number of interesting and important corollaries, such as the hyperdecidability of the pseudovariety of finite completely simple semigroups.
0 references