Zobrazeno 1 - 4
of 4
pro vyhledávání: '"Esa Sahla"'
Publikováno v:
Fundamenta Informaticae. 175:201-206
Denote by ш the operation of interleaving, or shuffling, of words. We prove that, given a regular language R and a letter-to-letter morphism φ, it is undecidable whether or not there exists a word ω such that ω ш φ(ω) ∩ R ≠ ø.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c30f7cab92a1c1af8b9ba42125cb1d13
https://doi.org/10.3233/fi-2020-1954
https://doi.org/10.3233/fi-2020-1954
Denote by ⧢ the operation of interleaving, or shuffling, of words. We prove that, given a regular language R and a letter-to-letter morphism ϕ, it is undecidable whether or not there exists a word w such that w ⧢ ϕ(w) ∩ R ≠ ∅.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4171911106faf1803c80def5c0dcc67c
https://doi.org/10.3233/stal200012
https://doi.org/10.3233/stal200012
Publikováno v:
Theoretical Computer Science. 732:85-88
We show that it is undecidable whether or not an injective rational function (realized by a finite transducer) f : A ⁎ → A ⁎ has a fixed point. The proof applies undecidability of the Post's Correspondence Problem for injective morphisms. As a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c30f44bde7ee85578758a38e8402b2fe
https://doi.org/10.1016/j.tcs.2018.04.030
https://doi.org/10.1016/j.tcs.2018.04.030
Publikováno v:
Fundamenta Informaticae. 154:167-176
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::733e2489ea0feaf6bc80787cee194a40
https://doi.org/10.3233/fi-2017-1558
https://doi.org/10.3233/fi-2017-1558