Макаров М. А. 
О перестановках, порожденных словами Штурма

Бесконечные перестановки (в нашем смысле) введены в работе [1]. В данной работе введен класс бесконечных перестановок, порожденных словами Штурма и по своим свойствам похожих на них. Найдена комбинаторная сложность, описаны графы Рози, частоты подперестановок и функции рекуррентности. Также найдены их арифметическая сложность и сложность Камаэ.

Makarov  M. A.
On the permutations generated by Sturmian words

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.

Полный текст статьи / Full texts:

• PDF file (410 KB)
• PostScript file (780 KB)