A1 Refereed original research article in a scientific journal
On Shuffling a Word with its Letter-to-Letter Substitution
Authors: Halava Vesa, Harju Tero, Sahla Esa
Publisher: IOS PRESS
Publication year: 2020
Journal: Fundamenta Informaticae
Journal name in source: FUNDAMENTA INFORMATICAE
Journal acronym: FUND INFORM
Volume: 175
Issue: 1-4
First page : 201
Last page: 206
Number of pages: 6
ISSN: 0169-2968
eISSN: 1875-8681
DOI: https://doi.org/10.3233/FI-2020-1954
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 ≠ ø.
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 ≠ ø.
UTU Research Portal