JUCS - Journal of Universal Computer Science 29(2): 100-117, doi: 10.3897/jucs.87330
Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words
expand article infoTrienko Grobler, Manfred Habeck, Lynette van Zijl, Jaco Geldenhuys
‡ Stellenbosch University, Stellenbosch, South Africa
Open Access

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.

Combinatorial generation, Combinatorics on words, Repetition, Upper bound