SC-hyperdecidability of \(\mathbf R\) (Q5941087)
From MaRDI portal
scientific article; zbMATH DE number 1635252
Language | Label | Description | Also known as |
---|---|---|---|
English | SC-hyperdecidability of \(\mathbf R\) |
scientific article; zbMATH DE number 1635252 |
Statements
SC-hyperdecidability of \(\mathbf R\) (English)
0 references
20 August 2001
0 references
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.
0 references
inevitable labellings
0 references
pseudovarieties of monoids
0 references
inevitability
0 references
labellings
0 references
pseudovarieties of finite groups
0 references
\(\mathcal R\)-trivial finite monoids
0 references
\(\mathcal L\)-trivial finite monoids
0 references
0 references