A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Equality sets of prefix morphisms and regular star languages
Tekijät: Halava V, Harju T, Latteux M
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2005
Lehti:: Information Processing Letters
Tietokannassa oleva lehden nimi: INFORMATION PROCESSING LETTERS
Lehden akronyymi: INFORM PROCESS LETT
Vuosikerta: 94
Numero: 4
Aloitussivu: 151
Lopetussivu: 154
Sivujen määrä: 4
ISSN: 0020-0190
DOI: https://doi.org/10.1016/j.ipl.2005.01.014
Tiivistelmä
We consider equality sets of prefix morphisms, that is, sets E(g(1), g(2)) = {w vertical bar g(1) (w) = g(2)(w)}, where g(1) and g(2) are prefix morphisms. Recall that a morphism g is prefix if, for all different letters a and b, g(a) is not a prefix of g(b). We prove a rather surprising equality on families of languages, namely, that the family of regular star languages coincides with the family of languages of form pi(A)(E(g(1), g(2))) for some prefix morphisms g(1) and g(2), and a projection pi(A) which deletes the letters not in A. (c) 2005 Elsevier B.V. All rights reserved.
We consider equality sets of prefix morphisms, that is, sets E(g(1), g(2)) = {w vertical bar g(1) (w) = g(2)(w)}, where g(1) and g(2) are prefix morphisms. Recall that a morphism g is prefix if, for all different letters a and b, g(a) is not a prefix of g(b). We prove a rather surprising equality on families of languages, namely, that the family of regular star languages coincides with the family of languages of form pi(A)(E(g(1), g(2))) for some prefix morphisms g(1) and g(2), and a projection pi(A) which deletes the letters not in A. (c) 2005 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali