The generation of longest optimal box repetition-free words
Date
2022-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
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.
Description
Thesis (MSc)--Stellenbosch University, 2022.
Keywords
Boxes, Combinatorial generation, Monte Carlo tree search, Box repetition free words, Hamiltonian systems, UCTD, Stochastic processes