Bibliography: pages 192-195 / The avoidability, or unavoidability of patterns in words over finite alphabets has
been studied extensively. The word α over a finite set A is said to be unavoidable
for an infinite set B+ of nonempty words over a finite set B if, for all but finitely
many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that
φ(α) is a factor of w.
In this treatise, we start by presenting a historical background of results that are
related to unavoidability. We present and discuss the most important theorems
surrounding unavoidability in detail.
We present various complexity-related properties of unavoidable words. For words
that are unavoidable, we provide a constructive upper bound to the lengths of
words that avoid them. In particular, for a pattern α of length n over an alphabet
of size r, we give a concrete function N(n, r) such that no word of length N(n, r)
over the alphabet of size r avoids α.
A natural subsequent question is how many unavoidable words there are. We show
that the fraction of words that are unavoidable drops exponentially fast in the
length of the word. This allows us to calculate an upper bound on the number of
unavoidable patterns for any given finite alphabet.
Subsequently, we investigate computational aspects of unavoidable words. In
particular, we exhibit concrete algorithms for determining whether a word is
unavoidable. We also prove results on the computational complexity of the problem
of determining whether a given word is unavoidable. Specifically, the
NP-completeness of the aforementioned problem is established. / Decision Sciences / D. Phil. (Operations Research)
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:unisa/oai:uir.unisa.ac.za:10500/27343 |
| Date | 12 1900 |
| Creators | Sauer, Paul Van der Merwe |
| Contributors | Fouche, Willem Louw, Potgieter, P. H. |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 1 online resource (195 pages), application/pdf |
Page generated in 0.0028 seconds