A1 Refereed original research article in a scientific journal
Equality sets of prefix morphisms and regular star languages
Authors: Halava V, Harju T, Latteux M
Publisher: ELSEVIER SCIENCE BV
Publication year: 2005
Journal:: Information Processing Letters
Journal name in source: INFORMATION PROCESSING LETTERS
Journal acronym: INFORM PROCESS LETT
Volume: 94
Issue: 4
First page : 151
Last page: 154
Number of pages: 4
ISSN: 0020-0190
DOI: https://doi.org/10.1016/j.ipl.2005.01.014
Abstract
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.
UTU Research Portal