Affiliations: [a] Complex Systems Research Group, Department of Mathematics and Statistics, University of Turku, Finland. [email protected] | [b] Department of Mathematics and Statistics, University of Turku, Finland. [email protected] | [c] Department of Mathematics and Statistics, University of Turku, Finland. [email protected]
Correspondence:
[†]
Address for correcpondence: Department of Mathematics and Statistics, University of Turku, Finland
Note: [*] Supported by emmy.network foundation under the aegis of the Fondation de Luxembourg.
Abstract: 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 ≠ ø.
