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 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

      Identifiers