Complete reducibility of systems of equations with respect to R.
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.
- Towards a pseudoequational proof theory
- Every decidable pseudovariety of abelian groups is completely tame
- Profinite topologies
- Recognizing pro-\(\mathrm{R}\) closures of regular languages
- Reducibility of pointlike problems
- Iterated periodicity over finite aperiodic semigroups
- Pointlike sets with respect to R and J.
- The pseudoidentity problem and reducibility for completely regular semigroups
- Factoriality and the Pin-Reutenauer procedure
- Complete κ-reducibility of pseudovarieties of the form DRH
- COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1
- Some reducibility properties for pseudovarieties of the form DRH
- Closures of regular languages for profinite topologies.
- The pseudovariety of all nilpotent groups is tame
- Reducibility vs. definability for pseudovarieties of semigroups
- Complete reducibility of pseudovarieties.
- Pseudovarieties of semigroups
- An automata-theoretic approach to the word problem for \(\omega\)-terms over R
This page was built for publication: Complete reducibility of systems of equations with respect to \(\mathbf R\).
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2479751)
