A1 Refereed original research article in a scientific journal
On quasi orders of words and the confluence property
Authors: Harju T, Ilie L
Publisher: ELSEVIER SCIENCE BV
Publication year: 1998
Journal:Theoretical Computer Science
Journal name in sourceTHEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 200
Issue: 1-2
First page : 205
Last page: 224
Number of pages: 20
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(97)00259-4
Abstract
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.
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.
UTU Research Portal