Complete words and superpatterns

This thesis surveys the most important results regarding complete words, by which we mean words containing as subsequences every permutation of some set, and then considers two variants of the problem of finding the shortest complete words. The first of these asks for the shortest superpattern, which is a complete word with some additional requirements, and the second asks for the expected number of timesteps before a particular random process generates a complete word.