inria-00178293, version 1
PATH-EQUIVALENT DEVELOPMENTS IN ACYCLIC WEIGHTED AUTOMATA
Dominique Lavenier
a, 1Giraud Mathieu 2Verber Philippe b, 1
International Journal of Foundations of Computer Science (IJFCS) 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 : SYMBIOSE (INRIA - IRISA)
- CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1
- 2 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
- CNRS : UMR8022 – INRIA – IRCICA – Université Lille 1 - Sciences et Technologies
- Domaine : Informatique/Architecture
Informatique/Informatique et langage - Mots-clés : Removal of ∊-transitions – partial removal – weighted finite automaton – hard-ware acceleration – chains of ∊-transitions
- inria-00178293, version 1
- http://hal.inria.fr/inria-00178293
- oai:hal.inria.fr:inria-00178293
- Contributeur : Dominique Lavenier
- Soumis le : Mercredi 10 Octobre 2007, 16:10:06
- Dernière modification le : Lundi 19 Octobre 2009, 16:07:50
Exporter