Subball complexity and Sturmian colorings of regular trees (Natural extension of arithmetic algorithms and S-adic system)

Abstract

The subball complexity of colorings of regular trees is a generalized of the subword complexity or factor complexity of infinite words. The Sturmian word which exhibits the smallest subword complexity among non-eventually periodic word can be obtained in geometric way using the irrational circle rotation or the projection of a line of irrational slope. We survey the Sturmian coloring or trees and the subball complexity of colorings of a tree associated to isometries of the hyperbolic plane with a tessellation of the hyperbolic plane.