Novel universal cycle constructions for a variety of combinatorial objects

dc.contributor.advisorSawada, Joe
dc.contributor.authorWong, Chi Him
dc.date.accessioned2015-05-06T13:24:48Z
dc.date.available2015-05-06T13:24:48Z
dc.date.copyright2015-04
dc.date.created2015-04-13
dc.date.issued2015-05-06
dc.degree.departmentSchool of Computer Scienceen_US
dc.degree.grantorUniversity of Guelphen_US
dc.degree.nameDoctor of Philosophyen_US
dc.degree.programmeComputer Scienceen_US
dc.description.abstractThe cyclic sequence 0000100110101111 has the unlikely property that the 16 unique binary substrings of length 4 appear exactly once in the sequence as a substring. This sequence is an example of a universal cycle. A universal cycle for an arbitrary set S is a cyclic sequence of length |S| whose substrings of length n encode |S| distinct instances in S. When S is the set of k-ary strings of length n, these sequences are commonly studied under the name de Bruijn sequence. Universal cycles have been studied for a wide variety of combinatorial objects including permutations, partitions, subsets, multisets, labeled graphs, various functions and passwords. The study of universal cycles has a long history with applications including dynamic connections in overlay networks, genomics, software calculation of the ruler function in computer words, and indexing a 1 in a computer word. There are standard proofs to demonstrate the existence of universal cycles for a variety of combinatorial objects; however, only a small number of universal cycles can be constructed efficiently and practically. This thesis provides novel efficient constructions to generate universal cycles for a variety of combinatorial objects. Our research leads to several new results. Firstly, we propose a novel shift rule to construct de Bruijn sequence for length n binary strings. The shift rule provides a simple and efficient successor rule to find the next bit in the de Bruijn sequence and is applicable to all values of n. We then extend the shift rule to construct de Bruijn sequence for k-ary strings of length n. Secondly, we generalize the Fredricksen-Kessler-Maiorana (FKM) construction and Greedy construction to generate universal cycles for a broad class of k-ary strings. We also prove that the universal cycles produced are the lexicographically smallest for the sets. Lastly, we provide the first known efficient construction to generate universal cycles for length n binary strings where the number of 1s range from c to d given 0 <= c < d <= n. We also prove the existence of universal cycles for other combinatorial objects including subsets of passwords and labeled graphs.en_US
dc.identifier.urihttp://hdl.handle.net/10214/8812
dc.language.isoenen_US
dc.publisherUniversity of Guelphen_US
dc.rights.licenseAll items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.
dc.subjectuniversal cycleen_US
dc.subjectde Bruijn sequenceen_US
dc.subjectcombinatorics on wordsen_US
dc.subjectFKM algorithmen_US
dc.subjectshift ruleen_US
dc.subjectnecklace prefix algorithmen_US
dc.subjectGray codeen_US
dc.subjectCAT algorithmen_US
dc.subjectGreedy algorithmen_US
dc.subjectsuccessor ruleen_US
dc.subjectnonlinear feedback shift registeren_US
dc.titleNovel universal cycle constructions for a variety of combinatorial objectsen_US
dc.typeThesisen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Wong_ChiHim_201505_PhD.pdf
Size:
1.05 MB
Format:
Adobe Portable Document Format