Trienko Grobler‡, Manfred Habeck‡, Lynette van Zijl‡, Jaco Geldenhuys‡Corresponding author: Lynette van Zijl ( lvzijl@sun.ac.za ) © Trienko Grobler, Manfred Habeck, Lynette van Zijl, Jaco Geldenhuys. This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY-ND 4.0). This license allows reusers to copy and distribute the material in any medium or format in unadapted form only, and only so long as attribution is given to the creator. The license allows for commercial use. Citation:
Grobler T, Habeck M, van Zijl L, Geldenhuys J (2023) Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words. JUCS - Journal of Universal Computer Science 29(2): 100-117. https://doi.org/10.3897/jucs.87330 |  |
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.