Word assembly through minimal forbidden words

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

Word assembly through minimal forbidden words

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

Matematica e Informatica

Risultato della ricerca: Article

22 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

Fingerprint

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Cita questo

Sciortino, M., Restivo, A., Fici, G., Fici, G., & Mignosi, F. (2006). Word assembly through minimal forbidden words. Theoretical Computer Science, 359, 214-230.

@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 = "Marinella Sciortino and Antonio Restivo and Gabriele Fici 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 - 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 -

Accesso al documento

OA Link