Complexity and decomposition to the set of factors

Svetlana Puzynina

Ancienne Post-doctorante – ENS Lyon  / LIP

→ du 01/10/2014 au 30/09/2016

Abstract: In this poster we introduce a new hierarchy of classes of languages and infinite words and its connection with complexity classes. Namely, we say that a language belongs to the class Lk if each word in it can be introduced as a catenation of k words from a language S, such that the number of words of length n in S is bounded by a constant. The class of infinite words whose set of factors is in Lk is denoted by Wk. In this talk we focus on the relations between the classes Wk and the subword complexity of infinite words, which is as usual defined as the number of factors of the word of length n. In particular, we prove that the class Wk coincides with the class of infinite words of linear complexity. On the other hand, although the class Wk is included in the class of words of complexity O(nk-1), this inclusion is strict for k≥ 2.

Keywords : infinite words, periodicity, complexity

Télécharger le poster [PDF – 267 Ko]

>> En savoir plus sur cette ancienne post-doctorante