Maximal pattern complexity of words over ℓℓ letters

The maximal pattern complexity function pα∗(k) of an infinite word α=α0α1α2⋯α=α0α1α2⋯ over ℓℓ letters, is introduced and studied by [3] and [4].In the present paper we introduce two new techniques, the ascending chain of alphabets and the singular decomposition  , to study the maximal pattern complexity. It is shown that if pα∗(k)<ℓk holds for some k≥1k≥1, then αα is periodic by projection. Accordingly we define a pattern Sturmian word   over ℓℓ letters to be a word which is not periodic by projection and has maximal pattern complexity function pα∗(k)=ℓk. Two classes of pattern Sturmian words are given. This generalizes the definition and results of [3] where ℓ=2ℓ=2.