Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words

Abstract

A bordered box repetition-free word is a finite word w where any given factor of the form asa, with a ∈ Σ and s ∈ Σ∗, occurs at most once. Four existing search algorithms are adapted to search for long bordered box repetition-free words over a given alphabet, giving an empirical result on the upper bound of the length of these words. Two algorithms use a tree-based search space, whilst the other two use a graph-based search space. For larger alphabets, the search space rapidly becomes intractable for the tree-based algorithms. In the case of the graph-based algorithms, we show a unique graph representation of bordered boxes that makes it possible to find long bordered box repetition-free words over a larger alphabet. The effectiveness of the four search algorithms are compared, and their respective worst case time complexities are compared against their performance in practice.

Keywords

• Combinatorial generation
• Combinatorics on words