-
- OTA Takahiro
- School of Network and Information, Senshu University
-
- MANADA Akiko
- Dept. of Electrical, Electronics and Information Engineering, Nagaoka University of Technology
Abstract
<p>A circular string formed by connecting the first and the last symbols of a string is one of the simplest sequence forms, and it has been used for many applications such as data compression and fragment assembly problem. A sufficient condition on the lengths of substrings with frequencies for reconstruction of an input circular binary string is shown. However, there are no detailed descriptions on the proof of the sufficient condition and reconstruction algorithm. In this paper, we prove a necessary and sufficient condition on the lengths of substrings with frequencies for reconstruction of the circular string. We show the length is shorter than that of previous study for some circular strings. For improving the length, we use minimal absent words (MAWs) for given substrings of length k, and we propose a new construction algorithm of MAWs of length h(>k) while a conventional construction algorithm of MAWs can construct MAWs of length ℓ(≤k). Moreover, we propose reconstruction algorithm of an input circular string for given substrings satisfying the new condition.</p>
Journal
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E107.A (3), 409-416, 2024-03-01
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390017843890682240
-
- ISSN
- 17451337
- 09168508
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
-
- Abstract License Flag
- Disallowed