Path-equivalent developments in acyclic weighted automata

Mathieu Giraud 1, 2, * Philippe Veber 3 Dominique Lavenier 3
* Auteur correspondant
2 SEQUOIA - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
3 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Weighted finite automata (WFA) are used with FPGA accelerating hardware to scan large genomic banks. Hardwiring such automata raises surface area and clock frequency constraints, requiring efficient ε-transitions-removal techniques. In this paper, we present bounds on the number of new transitions for the development of acyclic WFA, which is a special case of the ε-transitions-removal problem. We introduce a new problem, a partial removal of ε-transitions while accepting short chains of ε-transitions.
Type de document :
Article dans une revue
International Journal of Foundations of Computer Science, World Scientific Publishing, 2007, 18 (4), pp.799-812. 〈10.1142/S012905410700498X〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00271646
Contributeur : Mathieu Giraud <>
Soumis le : mercredi 9 avril 2008 - 18:11:56
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : jeudi 20 mai 2010 - 21:35:43

Fichier

gvl-ijfcs-07-preprint.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Mathieu Giraud, Philippe Veber, Dominique Lavenier. Path-equivalent developments in acyclic weighted automata. International Journal of Foundations of Computer Science, World Scientific Publishing, 2007, 18 (4), pp.799-812. 〈10.1142/S012905410700498X〉. 〈inria-00271646〉

Partager

Métriques

Consultations de la notice

749

Téléchargements de fichiers

146