The pseudovariety J is hyperdecidable
Let \(\mathbb{V}\) be a pseudovariety of finite semigroups generating the variety of all semigroups. Then the free semigroup \(A^+\) over any finite alphabet \(A=\{a_1,\ldots,a_n\}\) embeds into \(\overline F_n(\mathbb{V})\), the projective limit of all \(A\)-generated members of \(\mathbb{V}\) endowed with the product topology. The \(\mathbb{V}\)-closure of a language \(L\subseteq A^+\) is by definition the topological closure of \(L\) in \(\overline F_n(\mathbb{V})\). A labelling of (vertices and edges of) a directed graph \(\Gamma\) by elements of a semigroup \(S\) is said to be consistent if \(st=s'\) in \(S\) whenever \(t\) labels an edge whose initial [terminal] vertex is labelled \(s\) [resp., \(s'\)]. A pseudovariety \(\mathbb{V}\) generated by its monoids is called hyperdecidable if the following problem is decidable: given any finite directed graph \(\Gamma\) and any consistent labelling \(\lambda\) of \(\Gamma\) by elements of a finite semigroup \(S=\{s_1,\ldots,s_n\}\), to decide whether there exists a consistent labelling \(\overline\lambda\) of \(\Gamma\) by elements of \(\overline F_n(\mathbb{V})\) extending \(\lambda\) in the sense that the \(\overline\lambda\)-label of each vertex/edge of \(\Gamma\) is taken from the \(\mathbb{V}\)-closure of the language \(\varphi^{-1}(s)\) where \(s\) is the \(\lambda\)-label of that vertex/edge and \(\varphi\colon A^+\to S\) is the homomorphism extending the mapping \(a_i\mapsto s_i\), \(i=1,\ldots,n\). For the pseudovariety \(\mathbb{J}\) of all finite \(\mathcal J\)-trivial semigroups, the authors first show how to compute the \(\mathbb{J}\)-closure \(\overline L\) of a rational language \(L\subseteq A^+\), a result of independent interest. For this purpose, they construct from an automaton recognizing \(L\) a new automaton recognizing \(\overline L\) (this new automaton is labelled by elements of \(\overline F_n(\mathbb{J})\) rather than by letters). Then they check that the recognizable languages in \(\overline F_n(\mathbb{J})\) have some closure properties similar to those of languages in \(A^+\); in particular, finite intersections and quotients preserve recognizability. Finally, the authors express the problem from the definition of hyperdecidability as the emptiness problem for some languages in \(\overline F_n(\mathbb{J})\). Proofs heavily depend on the properties of certain factorizations of elements in \(\overline F_n(\mathbb{J})\) established by \textit{J.~Almeida} [see Chapter~8 in Finite semigroups and universal algebra. World Scientific (1995; Zbl 0844.20039)]. Corollaries include decidability results for the join \(\mathbb{J}\vee\mathbb{W}\) and the semidirect product \(\mathbb{J}*\mathbb{W}\), where \(\mathbb{W}\) stands for any pseudovariety such that, for every \(n\), there is an effectively computable bound for the order of \(n\)-generated semigroups in \(\mathbb{W}\).
- On the hyperdecidability of semidirect products of pseudovarieties
- ON THE HYPERDECIDABILITY OF PSEUDOVARIETIES OF GROUPS
- ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS
- ON THE DECIDABILITY OF THE MEMBERSHIP PROBLEM OF THE PSEUDOVARIETY J∨B
- HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
- Type II theorem and hyperdecidability of pseudovarieties of groups
- Irreducibility of certain pseudovarieties1
- On a locality-like property of the pseudovariety J
- scientific article; zbMATH DE number 1972777
- Complete reducibility of pseudovarieties.
- scientific article; zbMATH DE number 4008680 (Why is no real title available?)
- scientific article; zbMATH DE number 4028925 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 798167 (Why is no real title available?)
- 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 THE MEMBERSHIP PROBLEM OF THE PSEUDOVARIETY J∨B
- On the hyperdecidability of semidirect products of pseudovarieties
- Pointlike sets: the finest aperiodic cover of a finite semigroup
- The algebra of implicit operations
- Undecidability of the identity problem for finite semigroups
- Separability by piecewise testable languages is \textsc{PTime}-complete
- Profinite topologies
- Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon
- Pointlike sets with respect to R and J.
- Pointlike sets for varieties determined by groups
- Hyperdecidability of pseudovarieties of orthogroups
- On upper and lower bounds on the length of alternating towers
- On the hyperdecidability of semidirect products of pseudovarieties
- HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
- Some reducibility properties for pseudovarieties of the form DRH
- POLYNOMIAL CLOSURE AND TOPOLOGY
- ON THE HYPERDECIDABILITY OF PSEUDOVARIETIES OF GROUPS
- PROFINITE METHODS IN SEMIGROUP THEORY
- TAMENESS OF THE PSEUDOVARIETY OF ABELIAN GROUPS
- SC-hyperdecidability of R
- Conelikes and ranker comparisons
- First-order separation over countable ordinals
- Pseudovarieties of semigroups
- Pointlike sets and separation: a personal perspective
This page was built for publication: The pseudovariety $J$ is hyperdecidable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4385676)