A Reconstruction of Circular Binary String Using Substrings and Minimal Absent Words

DOI Web Site
  • OTA Takahiro
    School of Network and Information, Senshu University
  • MANADA Akiko
    Dept. of Electrical, Electronics and Information Engineering, Nagaoka University of Technology

抄録

<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>

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ