A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On Shuffling a Word with its Letter-to-Letter Substitution
Tekijät: Halava Vesa, Harju Tero, Sahla Esa
Kustantaja: IOS PRESS
Julkaisuvuosi: 2020
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: FUNDAMENTA INFORMATICAE
Lehden akronyymi: FUND INFORM
Vuosikerta: 175
Numero: 1-4
Aloitussivu: 201
Lopetussivu: 206
Sivujen määrä: 6
ISSN: 0169-2968
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-2020-1954
Tiivistelmä
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 ≠ ø.
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 ≠ ø.
Turun yliopiston Tutkimustietojärjestelmän portaali