Article ID Journal Published Year Pages File Type
10331325 Information Processing Letters 2005 4 Pages PDF
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
, , ,