Skip to Main content Skip to Navigation
Journal articles

Path-equivalent developments in acyclic weighted automata

Mathieu Giraud 1, 2, * Philippe Veber 3 Dominique Lavenier 3 
* Corresponding author
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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Mathieu Giraud Connect in order to contact the contributor
Submitted on : Wednesday, April 9, 2008 - 6:11:56 PM
Last modification on : Friday, February 4, 2022 - 3:25:13 AM
Long-term archiving on: : Thursday, May 20, 2010 - 9:35:43 PM


Publisher files allowed on an open archive



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⟩



Record views


Files downloads