A1 Refereed original research article in a scientific journal
Languages defined by generalized equality sets
Authors: Halava V, Harju T, Hoogeboom HJ, Latteux M
Publication year: 2003
Journal:: Lecture Notes in Computer Science
Journal name in source: FUNDAMENTALS OF COMPUTATION THEORY, PROCEEDINGS
Journal acronym: LECT NOTES COMPUT SC
Volume: 2751
First page : 355
Last page: 363
Number of pages: 9
ISBN: 3-540-40543-7
ISSN: 0302-9743
Abstract
We consider the generalized equality sets which are of the form E-G(a,g(1),g(2)) = {w \ g(1)(w) = ag(2)(w)}, determined by instances of the generalized Post Correspondence Problem, where the morphisms g(1) and g(2) are nonerasing 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 J is a shifted equality set of the above form. WE prove several closure properties for this family.
We consider the generalized equality sets which are of the form E-G(a,g(1),g(2)) = {w \ g(1)(w) = ag(2)(w)}, determined by instances of the generalized Post Correspondence Problem, where the morphisms g(1) and g(2) are nonerasing 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 J is a shifted equality set of the above form. WE prove several closure properties for this family.
UTU Research Portal