TAMENESS OF THE PSEUDOVARIETY LS1
The concept of `\(\kappa\)-tameness' was introduced by Almeida and Steinberg in the context of pseudovarieties of semigroups. It refines the well known concept of `decidability'. Several pseudovarieties are known to be tame such as: \(\mathbf G\), the pseudovariety of finite groups; \(\mathbf{Ab}\), the pseudovariety of finite Abelian groups; and \(\mathbf D\), the pseudovariety of finite semigroups whose idempotents are right zeros. In this paper, the authors prove the tameness of \(\mathbf{LSl}\), the pseudovariety of finite local semilattices or the pseudovariety of finite semigroups \(S\) such that \(eSe\in\mathbf{Sl}\) for all idempotents \(e\in S\). Here \(\mathbf{Sl}\) denotes the pseudovariety of finite semilattices. Proving the \(\kappa\)-tameness of \(\mathbf{LSl}\) involves proving the following two properties: first, the property that the \(\kappa\)-word problem for \(\mathbf{LSl}\) is decidable (which was proved earlier by the first author); and second, the property that \(\mathbf{LSl}\) is \(\kappa\)-reducible (which is proved in this paper). It is known that the pseudovariety \(\mathbf{LSl}\) is equal to the semidirect product \(\mathbf{Sl}*\mathbf D\) and is associated with the class of locally testable languages via Eilenberg's correspondence.
- Tameness of Some Locally Trivial Pseudovarieties
- Semidirect product with an order-computable pseudovariety and tameness.
- Tameness of joins involving the pseudovariety of local semilattices.
- Every decidable pseudovariety of abelian groups is completely tame
- Reducibility of Joins Involving Some Locally Trivial Pseudovarieties
- Algebraic decision procedures for local testability
- Characterizations of locally testable events
- Free profinite locally idempotent and locally commutative semigroups
- HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
- INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
- On the Decidability of Iterated Semidirect Products with Applications to Complexity
- Reducibility of Joins Involving Some Locally Trivial Pseudovarieties
- Some key problems on finite semigroups
- Tameness of Some Locally Trivial Pseudovarieties
- The Birkhoff theorem for finite algebras
- Undecidability of the identity problem for finite semigroups
- UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
- Towards a pseudoequational proof theory
- Every decidable pseudovariety of abelian groups is completely tame
- Profinite topologies
- Pointlike reducibility of pseudovarieties of the form V* D.
- McCammond’s normal forms for free aperiodic semigroups revisited
- On -reducibility of pseudovarieties of the form V D
- COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1
- Tameness of Some Locally Trivial Pseudovarieties
- Tameness of joins involving the pseudovariety of local semilattices.
- Semigroup presentations for test local groups.
- Tameness of pseudovariety joins involving R.
This page was built for publication: TAMENESS OF THE PSEUDOVARIETY LS1
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4658703)