Complete reducibility of systems of equations with respect to \(\mathbf R\). (Q2479751)

From MaRDI portal
Revision as of 00:22, 11 February 2024 by RedirectionBot (talk | contribs) (‎Removed claims)
scientific article
Language Label Description Also known as
English
Complete reducibility of systems of equations with respect to \(\mathbf R\).
scientific article

    Statements

    Complete reducibility of systems of equations with respect to \(\mathbf R\). (English)
    0 references
    3 April 2008
    0 references
    It is shown that the pseudovariety \(\mathbf R\) of all finite \(\mathcal R\)-trivial semigroups is completely reducible with respect the canonical signature. A pseudoword is an element of the \(A\)-generated free profinite semigroup \(\overline\Omega_AS\), where \(A\) is a finite alphabet and \(S\) is a semigroup. A semigroup \(S\) satisfies the pseudoidentity \(u=v\), if \(\varphi(u)=\varphi(v)\) for any continuous morphism \(\varphi\colon\overline\Omega_AS\to S\). Let \(\sigma\) be a set of pseudowords, called an implicit signature. The pseudovariety \(\mathbf V\) is \(\sigma\)-reducible for a class of equation systems if the existence of a solution modulo \(\mathbf V\) of any system in the class entails the existence of a solution in \(\sigma\)-terms. The signature \(\sigma\) should also possess reasonable algorithmic properties, (1) as a set, \(\sigma\) should be recursively enumerable; (2) as implicit operations, the elements of \(\sigma\) should be effectively computable in finite semigroups; (3) the word problem for the free \(\sigma\)-algebra in the variety generated by \(\mathbf V\) should be decidable. A pseudovariety is completely \(\sigma\)-reducible if it is \(\sigma\)-reducible for all finite systems of pseudoword equations in which the pseudowords that define the equations are given by \(\sigma\)-terms. The implicit signature most often consists of just two pseudowords: \(ab\), representing semigroup multiplication, and \(a^{\omega-1}\), the unary pseudoinverse. This signature is called canonical and denoted by \(\kappa\). The main result: The pseudovariety \(\mathbf R\) is completely \(\kappa\)-reducible.
    0 references
    \(\mathcal R\)-trivial semigroups
    0 references
    complete reducibility
    0 references
    relatively free profinite semigroups
    0 references
    pseudowords
    0 references
    systems of equations
    0 references
    implicit signatures
    0 references
    rational constraints
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references