On-line & Incremental Update Properties of the Subsequence Automaton - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

On-line & Incremental Update Properties of the Subsequence Automaton

Résumé

Many works deal with the subsequence matching problem using automata structures. It is to decide, given two sequences $s$ and $t$, whether $s$ is a subsequence of $t$. Automata like the Directed Acyclic Subsequence Graph (DASG) or the Subsequence Automaton (SA) accept all subsequences of a set of texts. We focus on this last structure and provide some useful results upon dynamically updates of the SA. Indeed, sequences are indexed as soon as they are processed, allowing to dynamically add or to remove sequences from the set of indexed texts. Moreover, the highlight of these properties also makes it possible to update this automaton whenever a sequence of the set is modified.
Fichier principal
Vignette du fichier
iSA.pdf (211.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00257567 , version 1 (19-02-2008)

Identifiants

  • HAL Id : inria-00257567 , version 1

Citer

Alban Mancheron, Jean-Émile Symphor. On-line & Incremental Update Properties of the Subsequence Automaton. [Research Report] 2007, pp.13. ⟨inria-00257567⟩
124 Consultations
84 Téléchargements

Partager

Gmail Facebook X LinkedIn More