On-line & Incremental Update Properties of the Subsequence Automaton

Alban Mancheron 1, * Jean-Émile Symphor 2
* Auteur correspondant
1 SEQUOIA - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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.
Type de document :
Rapport
[Research Report] 2007, pp.13
Liste complète des métadonnées


https://hal.inria.fr/inria-00257567
Contributeur : Alban Mancheron <>
Soumis le : mardi 19 février 2008 - 16:56:42
Dernière modification le : vendredi 16 septembre 2016 - 15:07:05
Document(s) archivé(s) le : jeudi 20 mai 2010 - 22:51:21

Fichiers

iSA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00257567, version 1

Collections

Citation

Alban Mancheron, Jean-Émile Symphor. On-line & Incremental Update Properties of the Subsequence Automaton. [Research Report] 2007, pp.13. <inria-00257567>

Partager

Métriques

Consultations de
la notice

151

Téléchargements du document

105