Name
Abstract | ||
|---|---|---|
We prove that two-way transducers (both deterministic and non-deterministic) cannot compress normal numbers. To achieve this, we first show that it is possible to generalize compressibility from one-way transducers to two-way transducers. These results extend a known result: normal infinite words are exactly those that cannot be compressed by lossless finite-state transducers, and, more generally, by bounded-to-one non-deterministic finite-state transducers. We also argue that such a generalization cannot be extended to two-way transducers with unbounded memory, even in the simple form of a single counter. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.ic.2015.02.001 | Inf. Comput. |
Keywords | Field | DocType |
compression,normal numbers,two-way automata | Compressibility,Normality,Discrete mathematics,Combinatorics,Automaton,Mathematics,Normal number,Lossless compression | Journal |
Volume | Issue | ISSN |
241 | C | 0890-5401 |
Citations | PageRank | References |
3 | 0.52 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Olivier Carton | 1 | 381 | 40.97 |
| Pablo Ariel Heiber | 2 | 50 | 8.38 |