SC-hyperdecidability of R

DOI10.1016/S0304-3975(99)00329-1MaRDI QIDQ5941087zbMATH OpenFDO

Authors Jorge Almeida, Pedro V. Silva

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(99)00329-1

zbMATH Keywords

\(\mathcal L\)-trivial finite monoids\(\mathcal R\)-trivial finite monoidsinevitabilityinevitable labellingslabellingspseudovarieties of finite groupspseudovarieties of monoids

Mathematics Subject Classification ID

Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Review text

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.NEWLINENEWLINENEWLINEThe 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.

Recommendations

• Hyperdecidability of pseudovarieties of orthogroups
• HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
• The pseudovariety J is hyperdecidable
• TAMENESS OF THE PSEUDOVARIETY OF ABELIAN GROUPS
• On the hyperdecidability of semidirect products of pseudovarieties

Cites work

• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• Categories as algebra: An essential ingredient in the theory of monoids
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (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 Pointlike Sets and Joins of Pseudovarieties
• On the hyperdecidability of semidirect products of pseudovarieties
• Profinite categories and semidirect products
• The pseudovariety J is hyperdecidable

Cited in

(8)

• The \(\kappa\)-word problem over \(\mathsf{DRH}\)
• Profinite topologies
• Pointlike sets with respect to R and J.
• Complete κ-reducibility of pseudovarieties of the form DRH
• INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
• Conelikes and ranker comparisons
• Tameness of pseudovariety joins involving R.
• Pointlike sets and separation: a personal perspective

This page was built for publication: SC-hyperdecidability of \(\mathbf R\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941087)