The pseudovariety J is hyperdecidable

From MaRDI portal
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}\).











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)