Compression of enumerations and gain
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909650432032768 |
|---|---|
| author | Barmpalias, George Zhang, Xiaoyan Zhan, Bohua |
| author_facet | Barmpalias, George Zhang, Xiaoyan Zhan, Bohua |
| contents | We study the compressibility of enumerations in the context of Kolmogorov complexity, focusing on strong and weak forms of compression and their gain: the amount of auxiliary information embedded in the compressed enumeration. The existence of strong compression and weak gainless compression is shown for any computably enumerable (c.e.) set. The density problem of c.e. sets with respect to their prefix complexity is reduced to the question of whether every c.e. set is well-compressible, which we study via enumeration games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_03030 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Compression of enumerations and gain Barmpalias, George Zhang, Xiaoyan Zhan, Bohua Computation and Language Information Theory Logic We study the compressibility of enumerations in the context of Kolmogorov complexity, focusing on strong and weak forms of compression and their gain: the amount of auxiliary information embedded in the compressed enumeration. The existence of strong compression and weak gainless compression is shown for any computably enumerable (c.e.) set. The density problem of c.e. sets with respect to their prefix complexity is reduced to the question of whether every c.e. set is well-compressible, which we study via enumeration games. |
| title | Compression of enumerations and gain |
| topic | Computation and Language Information Theory Logic |
| url | https://arxiv.org/abs/2304.03030 |