Path-equivalent developments in acyclic weighted automata

Mathieu Giraud (1, 2) , Philippe Veber (3) , Dominique Lavenier (3)

1 LIFL - Laboratoire d'Informatique Fondamentale de Lille
2 SEQUOIA - Sequential Learning
3 SYMBIOSE - Biological systems and models, bioinformatics and sequences

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.

Mots clés: removal of ε-transitions; partial removal; weighted finite automaton; hardware acceleration; chains of ε-transitions

Domaines: Algorithme et structure de données [cs.DS]; Combinatoire [math.CO]

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