A Convexity-based Generalization of Viterbi for Non-Deterministic Weighted Automata
We propose a novel approach for the maxstring
problem in acyclic nondeterministic
weighted FSA’s, which is based on
a convexity-related notion of domination
among intermediary results, and which
can be seen as a generalization of the usual
dynamic programming technique for finding
the max-path (a.k.a. Viterbi approximation)
in such automata.
The 11th International Conference on Finite-State Methods and Natural Language Processing, St Andrews, Scotland (UK), July 15-17, 2013.