| Presentation | 2016-12-22 Reduction of Search Number for Equivalence Structure Extraction Under Equivalence Structure Conservation Assumption Seiya Satoh, Yoshinobu Takahashi, Hiroshi Yamakawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We consider $K$-tuples that are composed of IDs that identify $K$D sequences where the number of IDs is $N$. An equivalence structure (ES) is defined as a set of $K$-tuples that identify $K$D sequences considered equivalent. Whether or not two $K$D sequences are equivalent is determined based on their continuous subsequences. Since the number of possible $K$-tuples taken from $N$ IDs is $_N {mathrm P}_K$, the comparisons cause combinatorial explosion along with the increase of $K$. In this paper, we show that a $K$D ES can be generated from a $(K - 1)$-D ES when we have an assumption that a $(K - 1)$-D ES is a superset of a set of $(K-1)$-tuples that are taken from a $K$D ES removing the $k$th ID of all the $K$-tuples. In addition, we show that we can obtain ES's successively increasing $K$ and reduce the number of tuples to consider. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | equivalence structure / imitation learning / combinatorial explosion / speed-up / sequence data |
| Paper # | ISEC2016-87,COMP2016-48 |
| Date of Issue | 2016-12-14 (ISEC, COMP) |
| Conference Information | |
| Committee | COMP / ISEC |
|---|---|
| Conference Date | 2016/12/21(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Hiroshima University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiroo Itoh(Univ. of Electro-Comm.) / Masahiro Mambo(Kanazawa Univ.) |
| Vice Chair | Yuushi Uno(Osaka Pref. Univ.) / Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) |
| Secretary | Yuushi Uno(Seikei Univ.) / Kazuto Ogawa(Kobe Univ.) / Atsushi Fujioka(Toshiba) |
| Assistant | / Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Technical Committee on Information Security |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Reduction of Search Number for Equivalence Structure Extraction Under Equivalence Structure Conservation Assumption |
| Sub Title (in English) | |
| Keyword(1) | equivalence structure |
| Keyword(2) | imitation learning |
| Keyword(3) | combinatorial explosion |
| Keyword(4) | speed-up |
| Keyword(5) | sequence data |
| 1st Author's Name | Seiya Satoh |
| 1st Author's Affiliation | National Institute of Advanced Industrial Science and Technology(AIST) |
| 2nd Author's Name | Yoshinobu Takahashi |
| 2nd Author's Affiliation | University of Electro-Communications(University of Electro-Communications) |
| 3rd Author's Name | Hiroshi Yamakawa |
| 3rd Author's Affiliation | Dwango Artificial Intelligence Laboratory(Dwango AI Lab) |
| Date | 2016-12-22 |
| Paper # | ISEC2016-87,COMP2016-48 |
| Volume (vol) | vol.116 |
| Number (no) | ISEC-380,COMP-381 |
| Page | pp.pp.81-86(ISEC), pp.81-86(COMP), |
| #Pages | 6 |
| Date of Issue | 2016-12-14 (ISEC, COMP) |