论文标题
一个*最短的字符串解码，用于非数字半程
A* shortest string decoding for non-idempotent semirings
论文作者
论文摘要
在非数字半段上，单个最短路径算法对于加权有限状态自动机而不确定，因为这样的半连接不能保证存在最短路径。但是，在不一轴的半仪中，承认满足单调性条件的订单（例如加时度或日志半段），最短字符串的概念是明确定义的。我们描述了一种算法，该算法在此类半潮中找到了加权非确定性自动机的最短字符串，使用同等的确定性自动机（DFA）的最短距离作为*在伴侣IDEMPOTENT SEMIRING上执行的*搜索的启发式范围，这被证明可以返回最短的字符串。尽管DFA中可能有更多的状态，但如果“飞行”执行确定性，则该算法只需要访问其中的一小部分。
The single shortest path algorithm is undefined for weighted finite-state automata over non-idempotent semirings because such semirings do not guarantee the existence of a shortest path. However, in non-idempotent semirings admitting an order satisfying a monotonicity condition (such as the plus-times or log semirings), the notion of shortest string is well-defined. We describe an algorithm which finds the shortest string for a weighted non-deterministic automaton over such semirings using the backwards shortest distance of an equivalent deterministic automaton (DFA) as a heuristic for A* search performed over a companion idempotent semiring, which is proven to return the shortest string. While there may be exponentially more states in the DFA, this algorithm needs to visit only a small fraction of them if determinization is performed "on the fly".
