Problem 29: Strict Border Table of the Fibonacci Word

$ \def\tbord{\mathit{border}} \def\sbord{\mathit{stbord}} \def\tper{\mathit{period}} \def\dd{\dot{}\dot{}} \def\sa#1{\tt{#1}} $

The border table $\tbord$ (see Problem 19) of the infinite Fibonacci word $\mathbf{f}$ has a simple structure but values in its strict border table $\sbord$ (see Problem 25) look chaotic at first glance. The problem examines a simple relation between the two tables, which helps to quickly compute any individual value of the table $\sbord$.

Below are the tables of periods, borders and strict borders related to a prefix of the Fibonacci word. Values at index $\ell$ correspond to the prefix $\mathbf{f}[0\dd \ell-1]$ of length $\ell$.

$i$ 0 1 2 3 4 5 6 7 8 9 10

$x[i]$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{a}$ $\sa{b}$ $\sa{a}$

$\ell$ 0 1 2 3 4 5 6 7 8 9 10 11

$\tper[\ell]$ 1 2 2 3 3 3 5 5 5 5 5

$\tbord[\ell]$ -1 0 0 1 1 2 3 2 3 4 5 6

$\sbord[\ell]$ -1 0 -1 1 0 -1 3 -1 1 0 -1 6

Show how to compute in logarithmic time the $n$th element of the strict border table of the infinite Fibonacci word $\mathbf{f}$.

Examine positions where tables $\tbord$ and $\sbord$ match.

$i$		0	1	2	3	4	5	6	7	8	9	10
$x[i]$		$\sa{a}$	$\sa{b}$	$\sa{a}$	$\sa{a}$	$\sa{b}$	$\sa{a}$	$\sa{b}$	$\sa{a}$	$\sa{a}$	$\sa{b}$	$\sa{a}$
$\ell$	0	1	2	3	4	5	6	7	8	9	10	11
$\tper[\ell]$		1	2	2	3	3	3	5	5	5	5	5
$\tbord[\ell]$	-1	0	0	1	1	2	3	2	3	4	5	6
$\sbord[\ell]$	-1	0	-1	1	0	-1	3	-1	1	0	-1	6

125 Problems in Text Algorithms

Problem 29: Strict Border Table of the Fibonacci Word