SC-hyperdecidability of R

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. (C) 2001 Elsevier Science B.V. All rights reserved.