On-line & Incremental Update Properties of the Subsequence Automaton

Alban Mancheron 1, * Jean-Émile Symphor 2
* Corresponding author
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.
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/inria-00257567
Contributor : Alban Mancheron <>
Submitted on : Tuesday, February 19, 2008 - 4:56:42 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Thursday, May 20, 2010 - 10:51:21 PM

Files

iSA.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

233

Files downloads

142