FIX to Optimal Dynamic Sequence Representations

Level: Medium

In Section 5.2 we say that the n_l occurrences of the symbols of S^l contribute n_l lg(n/n_l)+O(n_l lg lg n / lg^2 n) bits in S^lev. This is correct only if we use a representation for S^lev we had omitted in the paper because it was technical (boring) and we incorrectly believed unnecessary.

A self-contained version of the paper can be obtained here. Look at the new Section 5.1.

Another smaller mistake is that the space redundancy cannot be made as small as n lg s / lg^c n nor O(n), but it stays o(n lg s).

An extended version with all those problems fixed and also with much new material, including a worst-case bounded version, is available in arXiv.