Two-dimensional Fibonacci words: tandem repeats and factor complexity

DOI10.1016/J.AAM.2023.102553MaRDI QIDQ6107832zbMATH OpenOpenAlexFDO

Authors

Publication date 3 July 2023

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.13977

zbMATH Keywords

Fibonacci arrays Fibonacci words tandems two-dimensional factor complexity two-dimensional morphic words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: If

x

is a non-empty string then the repetition

x x

is called a tandem repeat. Similarly, a tandem in a two dimensional array

X

is a configuration consisting of a same primitive block

W

that touch each other with one side or corner. In cite{Apostolico:2000}, Apostolico and Brimkov have proved various bounds for the number of tandems in a two dimensional word of size

m i m e s n

. Of the two types of tandems considered therein, they also proved that, for one type, the number of occurrences in an

m i m e s n

Fibonacci array attained the general upper bound,

m a t h c a l O (m^{2} n h s p a c e 0.1 c m m b o x l o g h s p a c e 0.1 c m n)

. In this paper, we derive an expression for the exact number of tandems in a given finite Fibonacci array

f_{m, n}

. As a required result, we derive the factor complexities of

f_{m, n}

,

m, n g e 0

and that of the infinite Fibonacci word

f_{i n f t y, i n f t y}

. Generations of

f_{i n f t y, i n f t y}

and

f_{m, n}

, for any given

m, n g e 1

using a two-dimensional homomorphism is also achieved.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Two-dimensional Fibonacci words: tandem repeats and factor complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6107832)