Combinatorical and Algebraic Structures Seminar

Date:	4.11.2008
Speaker:	Ľubomíra Balková, FJFI, České vysoké učení technické
Title:	Mirror Substitutions and Palindromic Sequences
Abstract:	We will introduce results of Bo Tan and suggest their possible application and generalization. It is readily seen that an infinite uniformly recurrent word containing infinitely many distinct palindromes has the language closed under mirror image map. Fixed points of primitive substitutions are examples of uniformly recurrent words. Bo Tan proved that if u is a fixed point of a primitive substitution over a two-letter alphabet, then u is closed under mirror image map if and only if u contains infinitely many distinct palindromes. We will describe the main tools -- mirror substitutions and conjugate substitutions -- and the main ideas of the proof of the above Bo Tan's statement. We will further mention how to recognize at first sight whether a primitive substitution has the language closed under mirror image map. Finally, we will answer a famous question by Hof, Knill, and Simon on the so-called substitutions of class P over a two-letter alphabet. Bo Tan, Mirror substitutions and palindromic sequences, Theoretical Computer Science {\bf 389} (2007), 118 - 124

Return to index.

last update: 27.9.2007, webmaster: Petr Ambrož