Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Graz University of Technology
2023-02-01
|
| Series: | Journal of Universal Computer Science |
| Subjects: | |
| Online Access: | https://lib.jucs.org/article/87330/download/pdf/ |
| _version_ | 1811161513501655040 |
|---|---|
| author | Trienko Grobler Manfred Habeck Lynette van Zijl Jaco Geldenhuys |
| author_facet | Trienko Grobler Manfred Habeck Lynette van Zijl Jaco Geldenhuys |
| author_sort | Trienko Grobler |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T06:15:34Z |
| format | Article |
| id | doaj.art-c8ab3f0e2aad45a4b20951da5e126a91 |
| institution | Directory Open Access Journal |
| issn | 0948-6968 |
| language | English |
| last_indexed | 2024-04-10T06:15:34Z |
| publishDate | 2023-02-01 |
| publisher | Graz University of Technology |
| record_format | Article |
| series | Journal of Universal Computer Science |
| spelling | doaj.art-c8ab3f0e2aad45a4b20951da5e126a912023-03-02T09:11:19ZengGraz University of TechnologyJournal of Universal Computer Science0948-69682023-02-0129210011710.3897/jucs.8733087330Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free WordsTrienko Grobler0Manfred Habeck1Lynette van Zijl2Jaco Geldenhuys3Stellenbosch UniversityStellenbosch UniversityStellenbosch UniversityStellenbosch UniversityA 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.https://lib.jucs.org/article/87330/download/pdf/Combinatorial generationCombinatorics on words |
| spellingShingle | Trienko Grobler Manfred Habeck Lynette van Zijl Jaco Geldenhuys Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words Journal of Universal Computer Science Combinatorial generation Combinatorics on words |
| title | Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words |
| title_full | Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words |
| title_fullStr | Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words |
| title_full_unstemmed | Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words |
| title_short | Search Algorithms for the Combinatorial Generation of Bordered Box Repetition-Free Words |
| title_sort | search algorithms for the combinatorial generation of bordered box repetition free words |
| topic | Combinatorial generation Combinatorics on words |
| url | https://lib.jucs.org/article/87330/download/pdf/ |
| work_keys_str_mv | AT trienkogrobler searchalgorithmsforthecombinatorialgenerationofborderedboxrepetitionfreewords AT manfredhabeck searchalgorithmsforthecombinatorialgenerationofborderedboxrepetitionfreewords AT lynettevanzijl searchalgorithmsforthecombinatorialgenerationofborderedboxrepetitionfreewords AT jacogeldenhuys searchalgorithmsforthecombinatorialgenerationofborderedboxrepetitionfreewords |