Abelian complexity function of the Tribonacci word

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Abstract: According to a result of Richomme, Saari and Zamboni, the abelian complexity of the Tribonacci word satisfies

h o^{m a t h r m a b} (n) i n 3, 4, 5, 6, 7

for each

n i n m a t h b b N

. In this paper we derive an automaton that evaluates the function

h o^{m a t h r m a b} (n)

explicitly. The automaton takes the Tribonacci representation of

n

as its input; therefore,

(h o^{m a t h r m a b} (n))_{n i n m a t h b b N}

is an automatic sequence in a generalized sense. Since our evaluation of

h o^{m a t h r m a b} (n)

uses

m a t h c a l O (l o g n)

operations, it is fast even for large values of

n

. Our result also leads to a solution of an open problem proposed by Richomme et al. concerning the characterization of those

n

for which

h o^{m a t h r m a b} (n) = c

with

c

belonging to

4, 5, 6, 7

. In addition, we apply the same approach on the

4

-bonacci word. In this way we find a description of the abelian complexity of the

4

-bonacci word, too.

Recommendations

Cited in

(9)

Describes a project that uses

Uses Software

This page was built for publication: Abelian complexity function of the Tribonacci word