Words Avoiding Patterns: Definitions
Age Let w be an omega-word. The age of w, denoted by Age w, is the set of all finite subwords of w.
Alphabet An alphabet is just a finite set. We usually use S or T or variants to denote alphabets. Elements of an alphabet are called letters and are usually denoted by a, b, c, etc.
Antichain Let P be a partially ordered set. An antichain is a set of pairwise incomparable elements of P.
Avoidable We say that w encounters pattern p if we can write w = ah(p)b for words a and b, and some substitution h where no letter maps to the empty word under h.. Otherwise, we say that w avoids p. Let a pattern p be fixed. Let S be an alphabet with k letters. If there are arbitrarily long words over S avoiding p, we say that p is avoidable on S.
Essence Let w be an omega-word. The essence of w, denoted by Ess w is the set of all finite subwords of w that appear in w as subwords infinitely often.
k-powers Any word of the form uu...u with u repeated k times is called a k-power. Thus a repetition is a 2-power.
Length The length of a word w, denoted by |w|, is equal to the number of letters in w. For example, the length of banana is 6.
Non-repetitive A word w over alphabet S is non-repetitive if we cannot write w=abbc, unless b is the empty word.
Occurrence Let y be a subword of w. One specific place where y shows up in w is called an occurrence of y in w. Formally, an occurrence of y in w is a triple <x,y,z> such that w=xyz.
Omega-word We call a countably infinite sequence of letters of S an omega-word over S.
Overlap-free A word w is overlap-free if we cannot write w=aBBbc where b is the first letter of B.
Perfect A set S is perfect if it is non-empty, closed and contains no isolated points.
Repetition Any word of the form uu where u is not the empty word word is called a repetition .
Strongly Avoidable A word w strongly avoids p= p1p2...pn if we cannot write w=aP1P2...Pnb where Pi is a permutation of Pj whenever pi = pj .
Substitution Let S and T be alphabets. A substitution h from S* to T* is a function generated by its values on S. That is, suppose w is a word over S, w=w1w2...wn Then h(w)=h(w1)h(w2)...h(wn). For example, we could give a substitution h from {1,2,3}* to {1,2,3}* by h(1)=123, h(2)=13, h(3)=2. In this case, h(123)=h(1)h(2)h(3)=123132.
Subword We say that u is a subword of v if v=xuy for some words x and y.
Word Formally, a word w over alphabet S is an element of the free monoid S* generated by the letters of S. We usually denote words by u, v, w, etc. Informally, we take a naive view of words as consisting of strings of symbols; thus the concatenation of two words u and v, written uv, is simply the string consisting of the letters of u followed by the letters of v. The empty word, with no letters, is denoted by e. In some contexts, we refer to a word as a pattern.