We give a linear-time algorithm to reconstruct a finite word w over a finite alphabet A of constant size starting from a finite set of factors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in previous papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis.
FICI G, MIGNOSI F, RESTIVO A, SCIORTINO M (2006). Word assembly through minimal forbidden words. THEORETICAL COMPUTER SCIENCE, 359(1-3), 214-230 [10.1016/j.tcs.2006.03.006].
Word assembly through minimal forbidden words
FICI, Gabriele;RESTIVO, Antonio;SCIORTINO, Marinella
2006-01-01
Abstract
We give a linear-time algorithm to reconstruct a finite word w over a finite alphabet A of constant size starting from a finite set of factors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in previous papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
Word assembly through minimal forbidden words.pdf
Solo gestori archvio
Dimensione
262.84 kB
Formato
Adobe PDF
|
262.84 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.