COLORINGS OF TREES WITH LINEAR, INTERMEDIATE AND EXPONENTIAL SUBBALL COMPLEXITY
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We study colorings of regular trees using subball complex- ity b(n), which is the number of colored n-balls up to color-preserving isomorphisms. We show that for any k-regular tree, for k > 1, there are colorings of intermediate complexity. We then construct colorings of linear complexity b(n) = 2n + 2. We also construct colorings induced from sequences of linear subword complexity which has exponential subball complexity.
Abstract
We study colorings of regular trees using subball complex- ity b(n), which is the number of colored n-balls up to color-preserving isomorphisms. We show that for any k-regular tree, for k > 1, there are colorings of intermediate complexity. We then construct colorings of linear complexity b(n) = 2n + 2. We also construct colorings induced from sequences of linear subword complexity which has exponential subball complexity.
참고문헌 (9)
- H. Bass, "Tree Lattices" (2001), Birkhauser
- J. Cassaigne, "Constructing in nite words of intermediate complexity, Developments in language theory", Lecture Notes in Comput. Sci., 2450, pp.173~184 (2003), Springer
- E. Coven, "Sequences with Minimal Block Growth", Math. Systems Theory, 7, pp.138~153 (1973)
- X. Droubay, "Palindromes and Sturmian words", Theoret. Comput. Sci, 223(1-2), pp.73~85 (1999)
- D. Kim, "Subword complexity and Sturmian colorings of regular trees", Ergodic Theory Dynam. Systems, 35(2), pp.461~481 (2015)
- 김형근, "TOEPLITZ SEQUENCES OF INTERMEDIATE COMPLEXITY", 대한수학회지, 48(2), pp.383~395 (2011), 대한수학회
- M. Lothaire, "Algebraic Combinatorics on Words" (2002), Cambridge University Press
- G. Rote, "Sequences with Subword complexity 2n", J. Number Theory, 46(2), pp.196~213 (1994)
- J. Serre, "Trees" (1980), Springer