The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Une chaîne circulaire formée en connectant le premier et le dernier symbole d'une chaîne est l'une des formes de séquence les plus simples et elle a été utilisée pour de nombreuses applications telles que la compression de données et les problèmes d'assemblage de fragments. Une condition suffisante sur les longueurs de sous-chaînes avec des fréquences pour la reconstruction d'une chaîne binaire circulaire d'entrée est présentée. Cependant, il n’existe pas de descriptions détaillées de la preuve de la condition suffisante et de l’algorithme de reconstruction. Dans cet article, nous prouvons une condition nécessaire et suffisante sur les longueurs des sous-chaînes avec des fréquences pour la reconstruction de la corde circulaire. Nous montrons que la longueur est plus courte que celle de l’étude précédente pour certaines cordes circulaires. Pour améliorer la longueur, nous utilisons un minimum de mots absents (MAW) pour des sous-chaînes de longueur donnée. k, et nous proposons un nouvel algorithme de construction de MAW de longueur h(>k) alors qu'un algorithme de construction conventionnel de MAW peut construire des MAW de longueur l(≤k). De plus, nous proposons un algorithme de reconstruction d'une chaîne circulaire d'entrée pour des sous-chaînes données satisfaisant la nouvelle condition.
Takahiro OTA
Senshu University
Akiko MANADA
Nagaoka University of Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Takahiro OTA, Akiko MANADA, "A Reconstruction of Circular Binary String Using Substrings and Minimal Absent Words" in IEICE TRANSACTIONS on Fundamentals,
vol. E107-A, no. 3, pp. 409-416, March 2024, doi: 10.1587/transfun.2023TAP0015.
Abstract: 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 l(≤k). Moreover, we propose reconstruction algorithm of an input circular string for given substrings satisfying the new condition.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2023TAP0015/_p
Copier
@ARTICLE{e107-a_3_409,
author={Takahiro OTA, Akiko MANADA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Reconstruction of Circular Binary String Using Substrings and Minimal Absent Words},
year={2024},
volume={E107-A},
number={3},
pages={409-416},
abstract={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 l(≤k). Moreover, we propose reconstruction algorithm of an input circular string for given substrings satisfying the new condition.},
keywords={},
doi={10.1587/transfun.2023TAP0015},
ISSN={1745-1337},
month={March},}
Copier
TY - JOUR
TI - A Reconstruction of Circular Binary String Using Substrings and Minimal Absent Words
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 409
EP - 416
AU - Takahiro OTA
AU - Akiko MANADA
PY - 2024
DO - 10.1587/transfun.2023TAP0015
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E107-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2024
AB - 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 l(≤k). Moreover, we propose reconstruction algorithm of an input circular string for given substrings satisfying the new condition.
ER -