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

Issue title: A Mosaic of Computational Topics: from Classical to Novel, Special Issue Dedicated to Jetty Kleijn on the Occasion of Her 65th Birthday

Guest editors: Maurice ter Beek, Maciej Koutny and Grzegorz Rozenberg

Article type: Research Article

Authors: Halava, Vesa^{a; *} | Harju, Tero^{b; †} | Sahla, Esa^c

Affiliations: [a] Complex Systems Research Group, Department of Mathematics and Statistics, University of Turku, Finland. vesa.halava@utu.fi | [b] Department of Mathematics and Statistics, University of Turku, Finland. tero.harju@utu.fi | [c] Department of Mathematics and Statistics, University of Turku, Finland. esa.sahla@utu.fi

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

DOI: 10.3233/FI-2020-1954

Journal: Fundamenta Informaticae, vol. 175, no. 1-4, pp. 201-206, 2020