A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On quasi orders of words and the confluence property
Tekijät: Harju T, Ilie L
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 1998
Lehti:Theoretical Computer Science
Tietokannassa oleva lehden nimiTHEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 200
Numero: 1-2
Aloitussivu: 205
Lopetussivu: 224
Sivujen määrä: 20
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(97)00259-4
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali