Word assembly through minimal forbidden words

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

Word assembly through minimal forbidden words

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

Matematica e Informatica

Risultato della ricerca: Article › peer review

24 Citazioni (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.

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)

Fingerprint Entra nei temi di ricerca di 'Word assembly through minimal forbidden words'. Insieme formano una fingerprint unica.

Cita questo

@article{7dad62fc59f34a79ab5f4e67169bb5ae,

title = "Word assembly through minimal forbidden words",

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.",

author = "Gabriele Fici and Marinella Sciortino and Antonio Restivo and Gabriele Fici and Filippo Mignosi",

year = "2006",

language = "English",

volume = "359",

pages = "214--230",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Word assembly through minimal forbidden words

AU - Fici, Gabriele

AU - Sciortino, Marinella

AU - Restivo, Antonio

AU - Fici, Gabriele

AU - Mignosi, Filippo

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10447/11127

M3 - Article

VL - 359

SP - 214

EP - 230

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -