ON QUASI ORDERS OF WORDS AND THE CONFLUENCE PROPERTY

We investigate the confluence property, that is, the property of a lan guage to contain, for any two words of it, one which is bigger, with r espect to a given quasi order on the respective free monoid, than each of the former two. This property is investigated mainly for regular a nd context-free languages. As a consequence of our study, we give an a nswer to an old open problem raised by Haines concerning the effective regularity of the sets of subwords. Namely, we prove that there are f amilies with a decidable emptiness problem for which the regularity of the sets of subwords is not effective. (C) 1998-Elsevier Science B.V. All rights reserved.