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].
Data di pubblicazione: | 2006 | |
Titolo: | Word assembly through minimal forbidden words | |
Autori: | ||
Citazione: | 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]. | |
Rivista: | ||
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.tcs.2006.03.006 | |
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. | |
Appare nelle tipologie: | 1.01 Articolo in rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
Word assembly through minimal forbidden words.pdf | N/A | Administrator Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.