On quasi orders of words and the confluence property

AbstractWe investigate the confluence property, that is, the property of a language to contain, for any two words of it, one which is bigger, with respect to a given quasi order on the respective free monoid, than each of the former two. This property is investigated mainly for regular and context-free languages. As a consequence of our study, we give an answer to an old open problem raised by Haines concerning the effective regularity of the sets of subwords. Namely, we prove that there are families with a decidable emptiness problem for which the regularity of the sets of subwords is not effective