A4 Refereed article in a conference publication
An undecidability result concerning periodic morphisms
Authors: Halava V, Harju T
Editors: Werner Kuich, Grzegorz Rozenberg, Arto Salomaa
Publication year: 2002
Journal: Lecture Notes in Computer Science
Book title : Developments in Language Theory
Journal name in source: DEVELOPMENTS IN LANGUAGE THEORY
Journal acronym: LECT NOTES COMPUT SC
Series title: Developments in Language Theory International Conference
Number in series: 5
Volume: 2295
First page : 304
Last page: 310
Number of pages: 7
ISBN: 978-3-540-43453-5
ISSN: 0302-9743
Abstract
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.
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.
UTU Research Portal