This article is cited in 17 papers

On the permutations generated by Sturmian words

M. A. Makarov

Novosibirsk State University, Faculty of Mechanics and Mathematics, Novosibirsk

Abstract: Infinite permutations of use in this article were introduced in [1]. Here we distinguish the class of infinite permutations that are generated by the Sturmian words and inherit their properties. We find the combinatorial complexity of these permutations, describe their Rauzy graphs, frequencies of subpermutations, and recurrence functions. We also find their arithmetic complexity and Kamae complexity.

Keywords: infinite permutation, Sturmian word, combinatorial complexity, Rauzy graph, arithmetic complexity, Kamae complexity.

UDC: 519.1

Received: 26.11.2007

 English version: Siberian Mathematical Journal, 2009, 50:4, 674–680

Bibliographic databases:

• 
• 
•