More Web Proxy on the site http://driver.im/
Abelian Complexity Function of the Tribonacci Word
Ondřej Turek
Nuclear Physics Institute
Academy of Sciences of the Czech Republic
25068 Řež
Czech Republic
and
Bogolyubov Laboratory of Theoretical Physics
Joint Institute for Nuclear Research
141980 Dubna
Russia
Abstract:
According to a result of Richomme, Saari and Zamboni, the abelian
complexity of the Tribonacci word satisfies ρab(n)
∈ {3, 4, 5, 6, 7} for
each n ∈ N.
In this paper we derive an automaton that evaluates the
function ρab(n) explicitly.
The automaton takes the Tribonacci
representation of n as its input;
therefore, (ρab(n))n∈N
is an automatic
sequence in a generalized sense. Since our evaluation
of ρab(n) uses
O(log 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 ρab(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.
Full version: pdf,
dvi,
ps,
latex
(Concerned with sequences
A000073
A000078
A080843
A216190
A254990
A255014.)
Received
October 7 2014; revised version received February 12 2015.
Published in Journal of Integer Sequences, February 14 2015.
Return to
Journal of Integer Sequences home page