论文标题
二维斐波那契单词：串联重复和因子复杂性
Two-dimensional Fibonacci Words: Tandem Repeats and Factor Complexity
论文作者
论文摘要
如果$ x $是非空字符串，则重复$ xx $称为串联重复。同样，二维数组中的串联$ x $是一种配置，该配置由相同的原始块$ W $组成，彼此或角相互接触。在\ cite {apostolico：2000}中，Apostolico和Brimkov在尺寸$ M \ times n $的二维词中证明了串联数量的各种界限。 Of the two types of tandems considered therein, they also proved that, for one type, the number of occurrences in an $m \times n$ Fibonacci array attained the general upper bound, $\mathcal{O}(m^{2}n \hspace{0.1cm} \mbox{log} \hspace{0.1cm} n)$.在本文中，我们在给定有限的fibonacci数组$ f_ {m，n} $中得出了一个表达式。作为必需的结果，我们得出了$ f_ {m，n} $，$ m，n \ ge 0 $和无限fibonacci Word $ f _ {\ infty，\ infty，\ infty} $的因子复杂性。对于任何给定的$ m，n \ ge 1 $，使用二维同质性也可以实现$ f _ {\ infty，\ infty，\ infty} $和$ f_ {m，n} $的$。
If $x$ is a non-empty string then the repetition $xx$ 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 \times n$. Of the two types of tandems considered therein, they also proved that, for one type, the number of occurrences in an $m \times n$ Fibonacci array attained the general upper bound, $\mathcal{O}(m^{2}n \hspace{0.1cm} \mbox{log} \hspace{0.1cm} 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 \ge 0$ and that of the infinite Fibonacci word $f_{\infty, \infty}$. Generations of $f_{\infty, \infty}$ and $f_{m,n}$, for any given $m,n \ge 1$ using a two-dimensional homomorphism is also achieved.
