Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331325 | Information Processing Letters | 2005 | 4 Pages |
Abstract
We consider equality sets of prefix morphisms, that is, sets E(g1,g2)={w|g1(w)=g2(w)}, where g1 and g2 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 ÏA(E(g1,g2)) for some prefix morphisms g1 and g2, and a projection ÏA which deletes the letters not in A.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Vesa Halava, Tero Harju, Michel Latteux,