Special Issue: Implementation and Application of Automata: Contributed PapersNo Access

PATH-EQUIVALENT DEVELOPMENTS IN ACYCLIC WEIGHTED AUTOMATA

MATHIEU GIRAUD

Bioinfo/Sequoia, LIFL, CNRS, INRIA Futurs, Université Lille 1, 59650 Villeneuve d'Ascq, France

Search for more papers by this author

PHILLIPE VEBER

Symbiose, IRISA, INRIA, Campus de Beaulieu, 35042 Rennes cedex, France

Search for more papers by this author

, and

DOMINIQUE LAVENIER

Symbiose, IRISA, CNRS, Campus de Beaulieu, 35042 Rennes cedex, France

Search for more papers by this author

https://doi.org/10.1142/S012905410700498XCited by:0 (Source: Crossref)

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.

Keywords:

References

A. V. Aho , R. Sethi and J. D. Ullman , Compilers, Principles, Techniques and Tools ( Addison Wesley , 1986 ) . Google Scholar
F. Coste and G. Kerbellec, A similar fragments merging approach to learn automata on proteins, 16th European Conference on Machine Learning Machine Learning (ECML 2005), LNCS 3720 (2005) pp. 522–529. Google Scholar
M. Giraud and D. Lavenier, Linear encoding scheme for weighted finite automata, 9th International Conference on Implementation and Application of Automata (CIAA 2004), LNCS 3317 (2004) pp. 146–155. Google Scholar
M. Giraud and D. Lavenier, Journal of Automata, Languages and Combinatorics 10, 265 (2005). Web of Science, Google Scholar
M. B. Gokhale and P. S. Graham , Reconfigurable Computing – Accelerating Computation with Field-Programmable Gate Arrays ( Springer , 2005 ) . Google Scholar
C. Hagenah and A. Muscholl, Computing ɛ-free NFA from regular expressions in ${\mathcal O}(n \log^2 (n))$ time, Mathematical Foundations of Computer Science (MFCS 1998), LNCS 1450 (1998) pp. 277–285. Google Scholar
J. Hromkovic, S. Seibert and T. Wilke, Translating regular expressions into small epsilon-free nondeterministic finite automata, 14th Symposium on Theoretical Aspects of Computer Science (STAGS 1997), LNCS 1200 (1997) pp. 55–66. Google Scholar
J. Hromkovic and G. Schnitger, NFAs With and Without ɛ-Transitions, 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), LNCS 3580 (2005) pp. 385–396. Google Scholar
Y. Lifshits, Information Processing Letters 85, 293 (2003), DOI: 10.1016/S0020-0190(02)00436-2. Crossref, Web of Science, Google Scholar
M. Mohri, International Journal of Foundations of Computer Science 13, 129 (2002), DOI: 10.1142/S0129054102000996. Link, Google Scholar
M. Mohri, Computational Linguistics 23, 269 (1997). Web of Science, Google Scholar
P. Quignonet al., Genome Biology 6, R83 (2005), DOI: 10.1186/gb-2005-6-10-r83. Crossref, Web of Science, Google Scholar
G. Schnitger, Regular Expressions and NFAs Without ɛ-Transitions, 23th Symposium on Theoretical Aspects of Computer Science (STACS 2006), LNCS 3884 (2006) pp. 432–443. Google Scholar
K. Thompson, Communications of the ACM 11, 419 (1968), DOI: 10.1145/363347.363387. Crossref, Web of Science, Google Scholar