On-line & Incremental Update Properties of the Subsequence Automaton

* 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.
Mots-clés :
Type de document :
Rapport
[Research Report] 2007, pp.13

Littérature citée [7 références]

https://hal.inria.fr/inria-00257567
Contributeur : Alban Mancheron <>
Soumis le : mardi 19 février 2008 - 16:56:42
Dernière modification le : mardi 6 mars 2018 - 14:58:01
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

Citation

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

Métriques

Consultations de la notice

188

Téléchargements de fichiers