Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
The generation of longest optimal box repetition-free words
Thesis (MSc)--Stellenbosch University, 2022.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2022
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613890115796992 |
|---|---|
| access_status_str | Open Access |
| author | Habeck, Manfred |
| author2 | Grobler, Trienko |
| author_browse | Grobler, Trienko Habeck, Manfred |
| author_facet | Grobler, Trienko Habeck, Manfred |
| author_sort | Habeck, Manfred |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2022. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/124592 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:43:19.203Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/124592 The generation of longest optimal box repetition-free words Habeck, Manfred Grobler, Trienko Van Zijl, Lynette Geldenhuys, Jaco Stellenbosch University. Faculty of Science. Dept. of Computer Science. Boxes Combinatorial generation Monte Carlo tree search Box repetition free words Hamiltonian systems UCTD Stochastic processes Thesis (MSc)--Stellenbosch University, 2022. ENGLISH ABSTRACT: This thesis focuses on a specific problem within the field of combinatorial generation, namely, the generation of box repetition-free words. A box is a word over a given alphabet, where the first symbol in the word is the same as the last symbol. For example, the word abaca is a box. A box can contain other boxes. The box abaca contains boxes aba and aca. Boxes can overlap, such as aba and aca in abaca. This work investigates the generation of the longest possible sequence of symbols, over a given alphabet, which does not contain any repeating boxes. We show that an exhaustive enumeration based on a brute force approach with backtracking is not feasible. That is, we checked if adding a symbol to a word would create a repeating box; if not, recursively add another symbol. This method will eventually find all valid words, but takes an unreasonable amount of time for larger alphabets. As a non-enumerative attempt to find individual valid words, the Monte Carlo tree search is used. The search is based on the assumption that prefixes with good past results will also give good results in the future. Based on an analysis of the properties of box repetition-free words, a new search is devised. Factors of words are mapped onto a graph, and all non-optimal edges removed. It is then shown that any Hamiltonian path on this graph will result in a longest optimal word. The results of this work show that backtracking fails to generate longest optimal words within a reasonable time for any alphabet with more than three symbols. The Monte Carlo tree search performs better than backtracking, finding optimal words for an alphabet size of four, but failing for larger alphabets. The new method outperforms both, and with a small optimization, is shown to generate longest optimal words up to an alphabet size of six. AFRIKAANSE OPSOMMING: Hierdie tesis fokus op ’n spesifieke probleem in die veld van kombinatoriese generasie, naamlik die generasie van boksherhalingsvrye woorde. ’n Boks is ’n woord oor ’n gegewe alfabet, waar die eerste simbool in die woord dieselfde is as die laaste simbool. Byvoorbeeld, die woord abaca is ’n boks. ’n Boks kan ander boksse bevat. Die boks abaca bevat bokse aba en aca. Bokse kan oorvleuel, soos aba en aca in abaca. Hierdie werk ondersoek die generasie van die langste moontlike reeks simbole, oor ’n gegewe alfabet, wat geen herhalende bokse bevat nie. Ons wys dat ’n volledige enumeratiewe soektog gebaseer op ’n brute krag benadering met terugsporing nie haalbaar is nie. Dit wil sˆe, ons het gekontroleer of die byvoeging van ’n simbool aan ’n wo ord ’n herhalende boks sal skep; indien nie, voeg ’n ander simbool rekursief by. Hierdie metode sal uiteindelik alle geldige woorde vind, maar neem ’n buitensporige hoeveelheid tyd vir groter alfabette. As ’n nie-enumeratiewe poging om individuele geldige woorde te vind, word die Monte Carlo boom soektogalgoritme gebruik. Die soektog is gebaseer op die aanname dat voorvoegsels met goeie vorige resultate ook in die toekoms goeie resultate sal lewer. Op grond van ’n ontleding van die eienskappe van boksherhalingsvrye woorde, word ’n nuwe soekalgoritme voorgestel. Faktore van woorde word op ’n grafiek afgebeeld, en alle nie-optimale oorgange word verwyder. Dit word dan aangetoon dat enige Hamiltonse pad op hierdie grafiek tot ’n langste optimale woord sal lei. Die resultate van hierdie werk toon dat terugsporing nie die langste optimale woorde binne ’n redelike tyd genereer vir enige alfabet met meer as drie simbole nie. Die Monte Carlo boomsoektog presteer beter as terugsporing, en vind optimale woorde vir ’n alfabetgrootte van vier, maar misluk vir groter alfabette. Die nuwe metode presteer beter as albei, en met ’n klein optimering kan dit die langste optimale woorde van ’n alfabetgrootte van ses genereer. Masters 2022-02-01T11:16:21Z 2022-04-29T09:21:18Z 2022-02-01T11:16:21Z 2022-04-29T09:21:18Z 2022-04 Thesis http://hdl.handle.net/10019.1/124592 en_ZA Stellenbosch University 96 pages application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Boxes Combinatorial generation Monte Carlo tree search Box repetition free words Hamiltonian systems UCTD Stochastic processes Habeck, Manfred The generation of longest optimal box repetition-free words |
| title | The generation of longest optimal box repetition-free words |
| title_full | The generation of longest optimal box repetition-free words |
| title_fullStr | The generation of longest optimal box repetition-free words |
| title_full_unstemmed | The generation of longest optimal box repetition-free words |
| title_short | The generation of longest optimal box repetition-free words |
| title_sort | generation of longest optimal box repetition free words |
| topic | Boxes Combinatorial generation Monte Carlo tree search Box repetition free words Hamiltonian systems UCTD Stochastic processes |
| url | http://hdl.handle.net/10019.1/124592 |
| work_keys_str_mv | AT habeckmanfred thegenerationoflongestoptimalboxrepetitionfreewords AT habeckmanfred generationoflongestoptimalboxrepetitionfreewords |