<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)
Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/21294 |
Date | January 2008 |
Creators | Chan, Kelvin |
Contributors | Bruha, Ivan, Computer Science |
Source Sets | McMaster University |
Language | English |
Detected Language | English |
Page generated in 0.0012 seconds