2011/11/06 by John C. Kieffer, Kieffer, J., Philippe Flajolet +3
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Methods in Verification #Information Theory (cs.IT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1111.1432
openalex publication_date 2011/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A binary string of length 2k induces the Boolean function of k variables whose Shannon expansion is the given binary string. This Boolean function then is representable via a unique reduced ordered binary decision diagram (ROBDD). The given binary string is fully recoverable from this ROBDD. We exhibit a lossless data compression algorithm in which a binary string of length a power of two is compressed via compression of the ROBDD associated to it as described above. We show that when binary strings of length n a power of two are compressed via this algorithm, the maximal pointwise redundancy/sample with respect to any s-state binary information source has the upper bound (4log2s+16+o(1))/log2n . To establish this result, we exploit a result of Liaw and Lin stating that the ROBDD representation of a Boolean function of k variables contains a number of vertices on the order of (2+o(1))2k/k.