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.
Lingua originale | English |
---|---|
pagine (da-a) | 214-230 |
Numero di pagine | 17 |
Rivista | Theoretical Computer Science |
Volume | 359 |
Stato di pubblicazione | Published - 2006 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)