Presentation | 2021-03-04 Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report) Tomoyuki Yamakami, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The logical depth of a piece of data has served as a complexity measure todescribe the amount of “useful” and "non-random" information stored in the data itself. This notion is quite different from any standard information-theoreticmeasure and it is originated from Kolmogorov complexity that normallytreats off-line static data sets and measures the amount of datadecompression. This notion of logical depth has further expanded tovarious models of computation in the past literature to accommodate the needs for handling different circumstances. Of all sorts of data forms, we targetstreaming data sets coming incessantly through communication channels and aim at measuring the amount of useful information in them viatheir compression and decompression. As a decompression procedure ofstreaming data, we run one-way (or real-time) quantum finite-stateautomata equipped with write-once output tapes (called transducers) to recoverthe desired information from the incoming data sets, introducing thenotions of quantum finite-state depth and shallowness that captureusefulness of the streaming data sets. We first layout ageneral setting of compression/decompression of streaming data and, using fundamental properties, we then argue the existence of deep andshallow data sets. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | quantum finite-state automataKolmogorov complexitylogical depthdata compressiondata decompressionquantum finite-state deepquantum finite-state shallow |
Paper # | IT2020-117,ISEC2020-47,WBS2020-36 |
Date of Issue | 2021-02-25 (IT, ISEC, WBS) |
Conference Information | |
Committee | WBS / IT / ISEC |
---|---|
Conference Date | 2021/3/4(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Online |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | Joint Meeting of WBS, IT, and ISEC |
Chair | Masanori Hamamura(Kochi Univ. of Tech.) / Tadashi Wadayama(Nagoya Inst. of Tech.) / Shoichi Hirose(Univ. of Fukui) |
Vice Chair | Takashi Shono(INTEL) / Masahiro Fujii(Utsunomiya Univ.) / Tetsuya Kojima(Tokyo Kosen) / Tetsuya Izu(Fujitsu Labs.) / Noboru Kunihiro(Tsukuba Univ.) |
Secretary | Takashi Shono(Okayama Univ. of Science) / Masahiro Fujii(National Defence Academy) / Tetsuya Kojima(Yamaguchi Univ.) / Tetsuya Izu(Saga Univ.) / Noboru Kunihiro(Tsukuba Univ.) |
Assistant | Duong Quang Thang(NAIST) / Masafumi Moriyama(NICT) / Masayuki Kinoshita(Chiba Univ. of Tech.) / Takahiro Ohta(Senshu Univ.) / Kazuki Yoneyama(Ibaraki Univ.) |
Paper Information | |
Registration To | Technical Committee on Wideband System / Technical Committee on Information Theory / Technical Committee on Information Security |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Streaming Data Compression and Decompression by One-Way Quantum Finite-State Automata, Leading to Quantum Finite-State Deep and Shallow Information (Preliminary Report) |
Sub Title (in English) | |
Keyword(1) | quantum finite-state automataKolmogorov complexitylogical depthdata compressiondata decompressionquantum finite-state deepquantum finite-state shallow |
1st Author's Name | Tomoyuki Yamakami |
1st Author's Affiliation | University of Fukui(U of Fukui) |
Date | 2021-03-04 |
Paper # | IT2020-117,ISEC2020-47,WBS2020-36 |
Volume (vol) | vol.120 |
Number (no) | IT-410,ISEC-411,WBS-412 |
Page | pp.pp.31-36(IT), pp.31-36(ISEC), pp.31-36(WBS), |
#Pages | 6 |
Date of Issue | 2021-02-25 (IT, ISEC, WBS) |