Structures. The universe is $\{0, \dots, \mathrm{size}-1\}$; the vocabulary is the list $arities$, symbol $i$ having arity $arities[i]$ $\ge 1$. Both the universe and the vocabulary may be empty. A relation is a finite set of tuples, each a list of elements. A formula that mentions a symbol outside the vocabulary does not fit the structure ($WH_B2_FirstOrder.Formula.Fits$) and is false in it [FG06, p. 76].

Words. The word of a structure ($Encodes$) lists the number of symbols, the arities, the size of the universe, and then, for each symbol, the number of its tuples followed by their entries. The tuples of a relation may be listed in any order without repetition; the yes-instances of every problem are independent of the order. The encoding is self-delimiting, so a structure may be followed by further entries, as in an instance $(\mathcal A, k)$.

Size. The size of the universe is written as a single number. The word therefore has $O(|\tau| + \sum_R |R|\cdot\mathrm{arity}(R))$ entries, whereas the size $\|\mathcal A\|$ [FG06, p. 74] ($Structure.norm$) counts the universe in unary. A reduction that ranges over the universe first restricts it to the elements occurring in the relations together with a bounded number of further elements. This preserves the answer, since elements that occur in no relation are interchangeable.