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 metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00271646
Contributor : Mathieu Giraud <>
Submitted on : Wednesday, April 9, 2008 - 6:11:56 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Thursday, May 20, 2010 - 9:35:43 PM

File

gvl-ijfcs-07-preprint.pdf
Publisher files allowed on an open archive

Identifiers

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⟩

Share

Metrics

Record views

915

Files downloads

213