Name
Abstract | ||
|---|---|---|
We the compare the number of phrases created by Ziv/Lempel '78 parsing of a binary sequence and of its reversal. We show that the two parsings can vary by a factor that grows st least as fast as the logarithm of the sequence length. We then show that under a suitable condition, the factor can even become polynomial, and argue that the condition may not be necessary. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1109/SEQUEN.1997.666926 | SEQUENCES '97 Proceedings of the Compression and Complexity of Sequences 1997 |
Keywords | Field | DocType |
computer science,probability,binary sequence,encoding,asymmetry,polynomials,polynomial,data compression,data structures,logarithm,grammars | Rule-based machine translation,Discrete mathematics,Combinatorics,Polynomial,Pseudorandom binary sequence,Parsing,Logarithm,Asymmetry,Mathematics | Conference |
ISBN | Citations | PageRank |
0-8186-8132-2 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. Cohn | 1 | 2 | 0.72 |
| H. Helfgott | 2 | 5 | 0.81 |