Word assembly through minimal forbidden words

Gabriele Fici, Marinella Sciortino, Antonio Restivo, Gabriele Fici, Filippo Mignosi

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)214-230
Number of pages17
JournalTheoretical Computer Science
Volume359
Publication statusPublished - 2006

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint Dive into the research topics of 'Word assembly through minimal forbidden words'. Together they form a unique fingerprint.

Cite this