Since sentences over any finite alphabet are encodable as bitstrings, without loss of generality we focus on the binary alphabet . denotes the empty string, B* the set of finite sequences over B, the set of infinite sequences over B, . x,y,z,z1,z2 stand for strings in . If then xy is the concatenation of x and y (e.g., if x=10000 and y=1111 then xy = 100001111). Let us order lexicographically: if x precedes y alphabetically (like in the example above) then we write or ; if x may also equal y then we write or (e.g., ). The context will make clear where we also identify with a unique nonnegative integer 1x (e.g., string 0100 is represented by integer 10100 in the dyadic system or 20=1*24+0*23+1*22+0*21+0*20 in the decimal system). Indices i,j,m,m0,m1,n,n0,t,t0 range over the positive integers, constants c,c0,c1 over the positive reals, f,g denote functions mapping integers to integers, log the logarithm with basis 2, for real r>0. For , 0.x stands for the real number with dyadic expansion x (note that 0.x0111....=0.x1=0.x10=0.x100... for , although ). For , l(x) denotes the number of bits in x, where for ; . xn is the prefix of x consisting of the first n bits, if , and x otherwise ( ). For those that contain at least one 0-bit, x' denotes the lexicographically smallest satisfying (x' is undefined for x of the form ). We write f(n)=O(g(n)) if there exists c,n0 such that for all n > n0.