REAL

Reconstructing words from subwords in linear time

Dress, A. W. M. and Erdős, Péter (2005) Reconstructing words from subwords in linear time. ANNALS OF COMBINATORICS, 8 (4). pp. 457-462. ISSN 0218-0006

[img] Text
DressErdos-AoC04.pdf
Restricted to Repository staff only

Download (149kB) | Request a copy

Abstract

Almost 30 years ago, M. Schützenberger and L. Simon established that two n-words with letters drawn from a finite alphabet having identical sets of subwords of length up to [n/2]+1 are identical. In the context of coding theory, V.I. Levenshtein elaborated this result in a series of papers. And further elaborations dealing with alphabets and sequences with reverse complementation have been recently developed by P.L. Erdos, P. Ligeti, P. Sziklai, and D.C. Torney. However, the algorithmic complexity of actually (re)constructing a word from its subwords has apparently not yet explicitly been studied. This paper augments the work of M. Schützenberger and L. Simon by showing that their approach can be reworked so as to provide a linear-time solution of this reconstruction problem in the original setting studied in their work.

Item Type: Article
Uncontrolled Keywords: Subwords; Reconstruction of words; Algorithmic complexity
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 06 Feb 2014 03:44
Last Modified: 06 Feb 2014 03:44
URI: http://real.mtak.hu/id/eprint/9918

Actions (login required)

Edit Item Edit Item