Publications
Detailed Information
Colorings of regular trees with linear subword complexity: first examples and properties
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 임선희
- Major
- 자연과학대학 수리과학부
- Issue Date
- 2013-08
- Publisher
- 서울대학교 대학원
- Keywords
- Trees ; colorings of trees ; subword complexity ; symbolic dynamics ; Sturmian sequences ; Sturmian colorings
- Description
- 학위논문 (석사)-- 서울대학교 대학원 : 수리과학부, 2013. 8. 임선희.
- 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.
- Language
- English
- Files in This Item:
- Appears in Collections:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.