Languages defined by generalized equality sets

: Halava V, Harju T, Hoogeboom HJ, Latteux M

: 2003

Lecture Notes in Computer Science

FUNDAMENTALS OF COMPUTATION THEORY, PROCEEDINGS

: LECT NOTES COMPUT SC

: 2751

: 355

: 363

: 9

: 3-540-40543-7

: 0302-9743

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.

Mathematics