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.
2006
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].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/11127
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 33
  • ???jsp.display-item.citation.isi??? 20
social impact