Equality sets of prefix morphisms and regular star languages



: Halava V, Harju T, Latteux M

Publisher: ELSEVIER SCIENCE BV

: 2005

: Information Processing Letters

: INFORMATION PROCESSING LETTERS

: INFORM PROCESS LETT

: 94

: 4

: 151

: 154

: 4

: 0020-0190

DOI: https://doi.org/10.1016/j.ipl.2005.01.014


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.



Last updated on 2025-14-10 at 09:53