A Convexity-based Generalization of Viterbi for Non-Deterministic Weighted Automata
Marc Dymetman · 2013
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. 1