On Shuffling a Word with its Letter-to-Letter Substitution



: Halava Vesa, Harju Tero, Sahla Esa

Publisher: IOS PRESS

: 2020

: Fundamenta Informaticae

: FUNDAMENTA INFORMATICAE

: FUND INFORM

: 175

: 1-4

: 201

: 206

: 6

: 0169-2968

: 1875-8681

DOI: https://doi.org/10.3233/FI-2020-1954(external)


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 ≠ ø.



Last updated on 2024-26-11 at 19:12