| Autor: |
Trienko Grobler, Manfred Habeck, Lynette van Zijl, Jaco Geldenhuys |
| Jazyk: |
angličtina |
| Rok vydání: |
2023 |
| Předmět: |
|
| Zdroj: |
Journal of Universal Computer Science, Vol 29, Iss 2, Pp 100-117 (2023) |
| Druh dokumentu: |
article |
| ISSN: |
0948-6968 |
| DOI: |
10.3897/jucs.87330 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
