A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Equality sets for recursively enumerable languages
Tekijät: Halava V, Harju T, Hoogeboom HJ, Latteux M
Kustantaja: EDP SCIENCES S A
Julkaisuvuosi: 2005
Lehti: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Tietokannassa oleva lehden nimi: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Lehden akronyymi: RAIRO-THEOR INF APPL
Vuosikerta: 39
Numero: 4
Aloitussivu: 661
Lopetussivu: 675
Sivujen määrä: 15
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita:2005035
Tiivistelmä
We consider shifted equality sets of the form E-G(a, g(1), g(2)) = {w | g(1)( w) = ag(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 subset of A* is a projection of a shifted equality set, that is, L = pi(A)(E-G(a, g(1), g(2))) for some ( nonerasing) morphisms g(1) and g(2) and a letter a, where pi(A) deletes the letters not in A. Then we deduce that recursively enumerable star languages coincide with the projections of equality sets.
We consider shifted equality sets of the form E-G(a, g(1), g(2)) = {w | g(1)( w) = ag(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 subset of A* is a projection of a shifted equality set, that is, L = pi(A)(E-G(a, g(1), g(2))) for some ( nonerasing) morphisms g(1) and g(2) and a letter a, where pi(A) deletes the letters not in A. Then we deduce that recursively enumerable star languages coincide with the projections of equality sets.
Turun yliopiston Tutkimustietojärjestelmän portaali