10 Weight Functions
10.1 Recap: Strings
Recall that an alphabet is a set of characters like \(\{0, 1\}\) is the alphabet for binary. A string is an ordered sequence of characters from a fixed alphabet. E.g. \(011011\) and \(00011\) are binary strings.
Additionally, \(\varepsilon\) will denote the empty string and multiplication of strings will be done by concatenation. E.g. \(011 \cdot 000 = 011000\).
For most examples that follow, we will work with binary strings of \(0\)s and \(1\)s unless otherwise specified.
10.2 Definition
Let \(S\) be a set of strings (e.g. all binary strings or all ternary strings). A weight function on \(S\) is a function \(f : S \to \mathbf{Z}\) satisfying:
- \(f(x) \ge 0\)
- \(f(uv) = f(u) + f(v)\) when \(u\) and \(v\) are two strings.
Example 10.1 The length \(l\) of a string is a weight. E.g. \(l(011) = 3, l(011 \cdot 10011) = l(011) + l(10011)\).
Example 10.2 \(f(s) =\) the number of \(1\)s in \(s\) is a weight. E.g. \(f(011) = 2\) and \(f(011 \cdot 10011) = f(011) + l(10011)\).
10.2.1 Key property
The definition of a weight means they behave kind of like a logarithm. Therefore, if we do \(x^{f(s)}\), we get a function which satisfies
\[ x^{f(uv)} = x^{f(u)} \cdot x^{f(v)}. \] This is why we are going to have a bunch of \(x\)s all over the next few sections.