Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Equality sets for recursively enumerable languages

Vesa HalavaTero HarjuHendrik Jan HoogeboomMichel 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 HalavaTero HarjuHendrik Jan HoogeboomMichel Latteux — 2010

RAIRO - Theoretical Informatics and Applications

We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter...

Page 1

Download Results (CSV)