On quasi orders of words and the confluence property



: Harju T, Ilie L

Publisher: ELSEVIER SCIENCE BV

: 1998

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 200

: 1-2

: 205

: 224

: 20

: 0304-3975

DOI: https://doi.org/10.1016/S0304-3975(97)00259-4


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



Last updated on 2025-13-10 at 13:35