| Presentation | 2022-07-21 A Data Compression Method Where The Codeword Is a Computer Program Generating The Data Mitsuharu Arimura, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The Kolmogorov complexity of a string is defined as the shortest length of the program on a Turing machine used to represent the string. On the other hand, it is proved that lambda calculus has the same computational power as the Turing machine. This paper proposes a data compression method using computer programs as the codeword. We use the Haskell programming language, which is a functional programming language implemented on the basis of the lambda calculus. As a computational model, we use a context-free grammar and its corresponding computer model, push-down automaton. A relationship between this program and these models is described. In addition to showing the universality of this coding for finite-state information sources, we also show that coding and decoding are possible in linear time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Data Compression / Kolmogorov Complexity / Functional Programming / Haskell / Context-Free Grammar / Pushdown Automaton |
| Paper # | IT2022-19 |
| Date of Issue | 2022-07-14 (IT) |
| Conference Information | |
| Committee | IT |
|---|---|
| Conference Date | 2022/7/21(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Okayama University of Science |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Freshman session, General |
| Chair | Tetsuya Kojima(Tokyo Kosen) |
| Vice Chair | Yasuyuki Nogami(Okayama Univ.) |
| Secretary | Yasuyuki Nogami(Saitamai Univ.) |
| Assistant | Takayuki Nozaki(Yamaguchi Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Information Theory |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Data Compression Method Where The Codeword Is a Computer Program Generating The Data |
| Sub Title (in English) | |
| Keyword(1) | Data Compression |
| Keyword(2) | Kolmogorov Complexity |
| Keyword(3) | Functional Programming |
| Keyword(4) | Haskell |
| Keyword(5) | Context-Free Grammar |
| Keyword(6) | Pushdown Automaton |
| 1st Author's Name | Mitsuharu Arimura |
| 1st Author's Affiliation | Shonan Institute of Technology(Shonan Inst. Tech.) |
| Date | 2022-07-21 |
| Paper # | IT2022-19 |
| Volume (vol) | vol.122 |
| Number (no) | IT-128 |
| Page | pp.pp.18-23(IT), |
| #Pages | 6 |
| Date of Issue | 2022-07-14 (IT) |