Time: 9.3.2021 13:00
Speaker: Esa Sahla, University of Turku
Title: Self-shuffles with substitutions
Abstract: In formal language theory the operation of shuffling has been an occurring concept for over half a century. The operation has been studied in the context of formal languages as well as computability and process algebras. In this talk we will present some basic results on word shuffling with emphasis on shuffling a word with itself, i.e. the self-shuffle. We will then focus on a variant of the self-shuffle where a word is shuffled with its image under a letter-to-letter substitution. We will show that for a given regular language R it is undecidable whether there exists a word such that the forementioned self-shuffle intersects with R. The problem is reduced to the Post Correspondence Problem with a brief overview of PCP itself.