Jump to Content

Algorithms for Weighted Finite Automata with Failure Transitions

International Conference of Implementation and Applications of Automata (CIAA) (2018), pp. 46-58
Google Scholar


In this paper we extend some key weighted finite automata (WFA) algorithms to automata with failure transitions (phi-WFAs). Failure transitions, which are taken only when no immediate\ match is possible at a given state, are used to compactly epresent automata and have many applications. An efficient intersection algorithm and a shortest distance algorithm (over R+) are presented as well as a related algorithm to remove failure transitions from a phi-WFA.