A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
An undecidability result concerning periodic morphisms
Tekijät: Halava V, Harju T
Toimittaja: Werner Kuich, Grzegorz Rozenberg, Arto Salomaa
Julkaisuvuosi: 2002
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Developments in Language Theory
Tietokannassa oleva lehden nimi: DEVELOPMENTS IN LANGUAGE THEORY
Lehden akronyymi: LECT NOTES COMPUT SC
Sarjan nimi: Developments in Language Theory International Conference
Numero sarjassa: 5
Vuosikerta: 2295
Aloitussivu: 304
Lopetussivu: 310
Sivujen määrä: 7
ISBN: 978-3-540-43453-5
ISSN: 0302-9743
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali