SC-hyperdecidability of R

• Type: Article in International Scientific Journal
• Date: 2001

Authors

Almeida, J (Author) FCUP; Silva, PV (Author) FCUP

Journal

Title: Theoretical Computer Science

Vol. 255

Pages: 569-591

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 8 Citations

ISI Web of Science

Scopus - 9 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-000-W2N

DOI: 10.1016/s0304-3975(99)00329-1

Abstract (EN): A class TC(X) of X-graphs is introduced, and an algorithmic property of labellings of finite strongly connected graphs by rational languages is shown to be decidable. This property, named as TC-inevitability, is a language theoretic analogue of the R-inevitability of labellings of finite strongly connected graphs by finite monoids. As a consequence, the pseudovariety R of all finite R-trivial monoids is shown to be hyperdecidable relative to the class of labellings of finite strongly connected graphs by finite monoids. Strong decidability of the dual pseudovariety L follows as a corollary and a few applications to decidability results are provided.

Language: English

Type (Professor's evaluation): Scientific