<p> This thesis defends the use of genetic algorithms (GA) to solve the maximum number of repetitions in a binary string. Repetitions in strings have significant uses in many different fields, whether it is data-mining, pattern-matching, data compression or computational biology 14]. Main extended the definition of repetition, he realized that in some cases output could be reduced because of overlapping repetitions, that are simply rotations of one another [10]. As a result, he designed the notion of a run to capture the maximal leftmost repetition that is extended to the right as much as possible. Franek and Smyth independently computed the same number of maximum repetition for strings of length five to 35 using an exhaustive search method. Values greater than 35 were not computed because of the exponential increase in time required. Using GAs we are able to generate string with very large, if not the maximum, number of runs for any string length. The ability to generate strings with large runs is an advantage for learning more about the characteristics of these strings. </p> / Thesis / Master of Science (MSc)

String-to-String Correction is the process of transforming some mutable string M into an exact copy of some other string (the target string T), using a shortest sequence of well-defined edit operations. The formal STRING-TO-STRING CORRECTION problem asks for the optimal solution using just two operations: symbol deletion, and swap of adjacent symbols. String correction problems using only swaps and deletions are computationally interesting; in his paper On the Complexity of the Extended String-to-String Correction Problem (1975), Robert Wagner proved that the String-to-String Correction problem under swap and deletion operations only is NP-complete for unbounded alphabets. In this thesis, we present the first careful examination of the binary-alphabet case, which we call Binary String-to-String Correction (BSSC). We present several special cases of BSSC for which an optimal solution can be found in polynomial time; in particular, the case where T and M have an equal number of occurrences of a given symbol has a polynomial-time solution. As well, we demonstrate and prove several properties of BSSC, some of which do not necessarily hold in the case of String-to-String Correction. For instance: that the order of operations is irrelevant; that symbols in the mutable string, if swapped, will only ever swap in one direction; that the length of the Longest Common Subsequence (LCS) of the two strings is monotone nondecreasing during the execution of an optimal solution; and that there exists no correlation between the effect of a swap or delete operation on LCS, and the optimality of that operation. About a dozen other results that are applicable to Binary String-to-String Correction will also be presented. / Graduate / 0984 / 0715 / tspreen@gmail.com

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: This thesis gives a broad overview of what artificial chemistries (ACs) are, a brief review of several ACs and their applications, and an in depth analysis of one speci c AC: the four-bit binary string system. The model designed by Banzhaf [1] for in silico examination was recreated using the Python programming language. The initial motivation was to identify an existing AC that could be used to elucidate the sequence-function relationship, which led to the simultaneous investigation of self-organization in AC systems [7]. The interest in sequence-function relationships stems from their importance for self-production of objects [35]. For self-replication to be possible in larger organizations, the components of the organization must be able to continuously produce themselves [3, 7]. We chose the four-bit binary string system for investigation because of its simple design and implementation, its ability to yield complex results from interactions between a small population of objects, and its analogy to the DNA{RNA{protein organisation. When a population of objects are allowed to continuously interact, self-production and self-organization occur, even in simple arti cial systems [7, 8]. The stability of the emergent organizations depends on the interactions of its components, which must be capable of self-production if they are to maintain the organization [27]. Self-production of objects depends on their sequence-function relationship, which determines their rate of replication when interacting with other objects. / AFRIKAANSE OPSOMMING: Hierdie tesis verskaf `n bree oorsig van die algemene aard van artifisiele chemies (ACs), `n kort opsomming van `n paar ACs en hul toepassings, en `n diepgaande analise van een spesifieke AC: die 4-bis binere stringstelsel. Die model wat Banzhaf [1] ontwerp het vir in silico eksperimentering is hier herskep in die Python programmeringstaal. Die aanvanklike motivering was om `n bestaande AC te identifiseer wat gebruik kon word om die sekwens-funksie verwantskap te ontrafel, en dit het gelei tot die gelyktydige ondersoek van self-organisasie in AC stelsels [7]. Ons belangstelling in sekwens-funksie verwantskappe spruit uit hul belang vir die selfproduksie van objekte [35]. Om selfreplisering in meer omvangryke organisasies moontlik te maak moet die komponente in staat wees om hulself eenstryk te produseer [3, 7]. Ons het `n 4-bis stelsel vir hierdie studie gekies omdat die ontwerp en implementering eenvoudig is, omdat interaksies binne `n klein populasie van objekte komplekse resultate gee, en omdat die stelsel se organisasie analoog aan die DNA-RNA-proteien organisasie is. Wanneer `n populasie van objekte toegelaat word om eenstryk op mekaar te reageer vind self-produksie en self-organisasie vanself plaas, selfs in eenvoudige artifsiele stelsels [7, 8]. Die stabiliteit van die emergente organisasies hang af van die interaksies tussen die komponente, wat self die vermoe tot selfproduksie moet he indien hulle die organisasie in stand wil hou [27]. Selfproduksie van objekte hang af van hul sekwens-funsieverwantskap, wat op hul beurt bepaal hoe vinnig hulle repliseer wanneer in interaksie met ander objekte.