Colorings of regular trees with linear subword complexity: first examples and properties

Abstract

정규트리의 채색의 부분단어 복잡도는 채색된 반지름 n인 부분트리의 채색의 수를 b(n)으로 정의한 것이다. 본 논문은 부분단어 복잡도를 이용하여 정규트리의 채색을 연구한 결과이다. 부분단어 복잡도가 선형함수인 채색을 중점적으로 다루었으며 특히 부분단어 복잡도가 2n+2인 것을 다루었다. 부분단어 복잡도가 2n인 양방향 무한수열 중 원 위의 회전으로 부터 얻어지는 것들을 이용해 이를 만들었다. 그리고 부분단어 복잡도가 2n인 일반적인 양방향 무한수열로 부터 얻어지는 채색의 기본적인 성질을 증명하였다.

We study colorings of regular trees using subword complexity b(n), which is the number of equivalence classes of colored n-balls. We focus on colorings of linear subword complexity, especially colorings with b(n)=2n+2. We construct some colorings induced by circle rotations and prove fundamental properties of such colorings.