Home

Понедельник 25 марта, 18-05, ауд. 203

Понедельник, 25 марта, ауд. 203. Начало в 18:05.

Докладчик: Juhani Karhumäki (University of Turku).

Тема: Variations of the Morse-Hedlund Theorem for $ k $-Abelian Equivalence.

Abstract

In this talk we investigate local to global phenomena for a new family of complexity functions of infinite words indexed by $ k \in \Ni \cup \{+\infty\} $ where $ \Ni $ demotes the set of positive integers. Two finite words $ u $ and $ v $ in $ A^* $ are said to be $ k $-Abelian equivalent if for all $ x\in A^* $ of length less than or equal to $ k, $ the number of occurrences of $ x $ in $ u $ is equal to the number of occurrences of $ x $ in $ v. $ This defines a family of equivalence relations $ \thicksim_k $ on $ A^*, $ bridging the gap between the usual notion of Abelian equivalence (when $ k=1 $) and equality (when $ k=+\infty $). Given an infinite word $ w \in A^\omega, $ we consider the associated complexity function $ \mathcal {P}^{(k)}_\omega :\Ni \rightarrow \Ni $ which counts the number of $ k $-Abelian equivalence classes of factors of $ w $ of length $ n. $ As a whole, these complexity functions have a number of common features: Each gives a characterization of periodicity in the context of bi-infinite words, and each can be used to characterize Sturmian words in the framework of aperiodic one-sided infinite words. Nevertheless, they also exhibit a number of striking differences, the study of which is one of the main topics of our talk. The talk is based on the join work with Aleksi Saarela and Luca Q. Zamboni.