Page 1

Displaying 1 – 4 of 4

Showing per page

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We consider shifted equality sets of the form E G ( a , g 1 , g 2 ) = { w g 1 ( w ) = a g 2 ( w ) } , where g 1 and g 2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h ( E G ( J ) ) , where h is a coding and E G ( J ) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L A * is a projection of a shifted equality set, that is, L = π A ( E G ( a , g 1 , g 2 ) ) for some (nonerasing) morphisms g 1 and g 2 and a letter a , where π A deletes the letters not in A . Then we deduce...

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2010)

RAIRO - Theoretical Informatics and Applications

We consider shifted equality sets of the form EG(a,g1,g2) = {ω | g1(ω) = ag2(ω)}, where g1 and g2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(EG(J)), where h is a coding and (EG(J)) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L ⊆ A* is a projection of a shifted equality set, that is, L = πA(EG(a,g1,g2)) for some (nonerasing) morphisms g1...

Currently displaying 1 – 4 of 4

Page 1