| Presentation | 2005-07-22 Construction Antidictionary of a Binary String Using Suffix Tree Takahiro OTA, Hiroyoshi MORITA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | An antidictionary is a set of shortest words that never appear in a binary string. To construct the antidictionary for a given string, a method used suffix trie has been known. But the complexity of the method is quadratic in both of time and space. In this article, we present an algorithm to construct antidictionary of a given string, based on suffix tree representation of the string. The proposed algorithm needs linear computional time and space. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | antidictionary / minimal forbidden word / suffix tree / linear / computional complexity |
| Paper # | IT2005-43 |
| Date of Issue |
| Conference Information | |
| Committee | IT |
|---|---|
| Conference Date | 2005/7/15(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Theory (IT) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Construction Antidictionary of a Binary String Using Suffix Tree |
| Sub Title (in English) | |
| Keyword(1) | antidictionary |
| Keyword(2) | minimal forbidden word |
| Keyword(3) | suffix tree |
| Keyword(4) | linear |
| Keyword(5) | computional complexity |
| 1st Author's Name | Takahiro OTA |
| 1st Author's Affiliation | Department of Electronic Engineering, Nagano Prefectural Institute of Technology() |
| 2nd Author's Name | Hiroyoshi MORITA |
| 2nd Author's Affiliation | Graduate School of Information Systems, University of Electro-Communications |
| Date | 2005-07-22 |
| Paper # | IT2005-43 |
| Volume (vol) | vol.105 |
| Number (no) | 191 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |