Tameness of pseudovariety joins involving R.
type: Item
instance of: scholarly article
title: Tameness of pseudovariety joins involving R.
zbMATH Open document ID: 1091.20036
author: José Carlos Costa
author: Marc Zeitoun
author: Jorge Almeida
published in: Monatshefte für Mathematik
publication date: 2006-02-07T00:00:00Z
review text: The concept of ``tameness'' (with respect to an implicit signature \(\sigma\)) has been much studied recently in the context of decidability of semidirect products of pseudovarieties of semigroups and monoids. Roughly speaking, \(\sigma\)-tameness of a pseudovariety \(\mathbf V\) consists of two ingredients: (i) the decidability of the word problem for the free \(\sigma\)-\(\mathbf V\)-semigroup and (ii) \(\sigma\)-reducibility of \(\mathbf V\). The latter means that each system of equations of a certain kind (defined by a graph theoretic condition) admits a solution (under certain constraints) in any member of \(\mathbf V\) only if it admits a corresponding solution in the free \(\sigma\)-\(\mathbf V\)-semigroup. In the main part of the paper, the authors prove that for the ``standard'' implicit signature \(\sigma=\kappa=\{\cdot,{}^{\omega-1}\}\), all pseudovariety joins of the form \(\mathbf R\vee\mathbf W\) with \({\mathbf W}\subseteq [\![xy^{\omega+1}z=xyz]\!]\), \(\mathbf W\) \(\kappa\)-tame, are \(\kappa\)-tame (and a fortiori are decidable). This, in particular, holds for the joins \(\mathbf R\vee\mathbf{Com}\), \(\mathbf R\vee\mathbf G\) and \(\mathbf R\vee\mathbf{CR}\). The proof is based on quite delicate arguments involving profinite combinatorics of the free pro-\(\mathbf R\)-trivial monoid. At the beginning of the paper some additional results concerning the complete \(\sigma\)-reducibility (and therefore complete \(\sigma\)-tameness) of joins with subpseudovarieties of \(\mathbf J\) are established, where ``complete'' refers to a generalization of that notion defined by allowing more general systems of equations. The reviewer was informed that in work under preparation a complete reducibility result for \(\mathbf R\) is obtained by the same authors.
reviewed by: K. Auinger
Mathematics Subject Classification ID: 20M07
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 5004425
zbMATH Keywords: completely tame pseudovarieties
zbMATH Keywords: completely reducible pseudovarieties
zbMATH Keywords: \(\mathbf R\)-trivial semigroups
zbMATH Keywords: joins of pseudovarieties
zbMATH Keywords: systems of equations
zbMATH Keywords: rational constraints
zbMATH Keywords: implicit operations
zbMATH Keywords: decidability
zbMATH Keywords: word problem
zbMATH Keywords: pseudoidentities
MaRDI profile type: Publication
full work available at URL: s00605-005-0324-1
OpenAlex ID: W2115749858
cites work: Undecidability of the identity problem for finite semigroups
cites work: Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon
cites work: Q4003594
cites work: HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
cites work: Q4407421
cites work: The join of the pseudovarieties of \(\mathcal R\)-trivial and \(\mathcal L\)-trivial monoids
cites work: PSEUDOVARIETY JOINS INVOLVING ${\mathscr J}$ -TRIVIAL SEMIGROUPS
cites work: TAMENESS OF THE PSEUDOVARIETY OF ABELIAN GROUPS
cites work: SC-hyperdecidability of \(\mathbf R\)
cites work: On the Decidability of Iterated Semidirect Products with Applications to Complexity
cites work: Q4942266
cites work: The pseudoidentity problem and reducibility for completely regular semigroups
cites work: An automata-theoretic approach to the word problem for \(\omega\)-terms over R
cites work: THE EQUATIONAL THEORY OF ω-TERMS FOR FINITE ${\mathcal R}$-TRIVIAL SEMIGROUPS
cites work: INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
cites work: On the extension problem for partial permutations
cites work: Q3351422
cites work: Reducibility of Joins Involving Some Locally Trivial Pseudovarieties
cites work: TAMENESS OF THE PSEUDOVARIETY LS1
cites work: Equations in free groups are not finitely approximable
cites work: Extending partial automorphisms and the profinite topology on free groups
cites work: Set theory. An introduction to independence proofs
cites work: Profinite semigroups, Mal'cev products, and identities
cites work: PROFINITE SEMIGROUPS, VARIETIES, EXPANSIONS AND THE STRUCTURE OF RELATIVELY FREE PROFINITE SEMIGROUPS
cites work: On Pointlike Sets and Joins of Pseudovarieties
cites work: Q4227139
DOI: 10.1007/S00605-005-0324-1
description: scientific article; zbMATH DE number 5004425