inria-00271646, version 1
Path-equivalent developments in acyclic weighted automata
Mathieu Giraud
a, 1, 2Philippe Veber b, 3Dominique Lavenier
a, 3
International Journal of Foundations of Computer Science 18, 4 (2007) 799-812
Résumé : 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.
- a – CNRS
- b – INRIA
- 1 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
- CNRS : UMR8022 – INRIA – IRCICA – Université Lille 1 - Sciences et Technologies
- 2 : SEQUOIA (INRIA Lille - Nord Europe)
- INRIA – CNRS : UMR8022 – Université Lille 1 - Sciences et Technologies – Université Charles de Gaulle - Lille III
- 3 : SYMBIOSE (INRIA - IRISA)
- CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
- Domaine : Informatique/Algorithme et structure de données
Mathématiques/Combinatoire - Mots-clés : removal of ε-transitions – partial removal – weighted finite automaton – hardware acceleration – chains of ε-transitions
- inria-00271646, version 1
- http://hal.inria.fr/inria-00271646
- oai:hal.inria.fr:inria-00271646
- Contributeur : Mathieu Giraud
- Soumis le : Mercredi 9 Avril 2008, 18:11:56
- Dernière modification le : Mercredi 9 Avril 2008, 20:58:53
Documents associés
Exporter