Name
Abstract | ||
|---|---|---|
This paper studies the pseudovariety R of all finite R-trivial semigroups. We give a representation of pseudowords over R by infinite trees, called R-trees. Then we show that a pseudoword is an ω-term if and only if its associated tree is regular (i.e. it can be folded into a finite graph), or equivalently, if the ω-term has a finite number of tails. We give a linear algorithm to compute a compact representation of the R-tree for ω-terms, which yields a linear solution of the word problem for ω-terms over R. We finally exhibit a basis for the ω-variety generated by R and we show that there is no finite basis. Several results can be compared to recent work of Bloom and Choffrut on long words. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2006.10.019 | Theoretical Computer Science |
Keywords | DocType | Volume |
Semigroup,Pseudovariety,Word problem,Automata minimization,Pseudoword,Omega-term,Identity basis | Journal | 370 |
Issue | ISSN | Citations |
1 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Almeida | 1 | 61 | 15.24 |
| Marc Zeitoun | 2 | 288 | 24.51 |