Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0304-3975(99)00329-1 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
R-trivial,Pseudovariety,Graph labelling,Monoid,Hyperdecidability,20M07,20M35 | Journal | 255 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 1 |
PageRank | References | Authors |
0.38 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Almeida | 1 | 61 | 15.24 |
| Pedro V. Silva | 2 | 141 | 29.42 |