An undecidability result concerning periodic morphisms

: Halava V, Harju T

: Werner Kuich, Grzegorz Rozenberg, Arto Salomaa

: 2002

: Lecture Notes in Computer Science

: Developments in Language Theory

: DEVELOPMENTS IN LANGUAGE THEORY

: LECT NOTES COMPUT SC

: Developments in Language Theory International Conference

: 5

: 2295

: 304

: 310

: 7

: 978-3-540-43453-5

: 0302-9743

The following universe problem for the equality sets is shown to be undecidable: given a weak coding h, and two morphisms g(1), g(2), where g(2) is periodic, determine whether or not h(E-G (g(1), g(2))) = Sigma(+), where E-G (g(1), g(2)) consists of the solutions w to the equation g(1) (w) = #g(2) (w) for a fixed letter #. The problem is trivially decidable, if instead of E-G (g(1), g(2)) the equality set E(g(1), g(2)) (without a marker symbol #) is chosen.

Mathematics