SC-hyperdecidability of \(\mathbf R\) (Q5941087): Difference between revisions

The notion of inevitability of a labelling of a graph by a monoid for the pseudovariety of finite groups was introduced by Ash, and the first author generalized this concept to an arbitrary pseudovariety \(\mathbf V\) of monoids. A labelling \(\phi\colon\Gamma\to M\) of a graph \(\Gamma\) by a monoid \(M\) is \(\mathbf V\)-inevitable, if for any relational morphism \(\mu\colon M\to N\) with \(N\in{\mathbf V}\), there exists a consistent labelling \(\phi'\colon\Gamma\to N\) such that \((\phi(a),\phi'(a))\in\mu\). A pseudovariety \(\mathbf V\) is called (SC-)hyperdecidable, if it is decidable whether a given labelling of a finite (strongly connected) graph by a finite monoid is \(\mathbf V\)-inevitable. The authors prove that the pseudovariety \(\mathbf R\) of all \(\mathcal R\)-trivial finite monoids is SC-hyperdecidable. As an application they show that both \(\mathbf R\) and the pseudovariety \(\mathbf L\) of all \(\mathcal L\)-trivial finite monoids are strongly decidable.