Semiring Frameworks and Algorithms for Shortest-Distance Problems

By Mehryar Mohri. J. Autom. Lang. Comb., 2002

372 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/3860e0242db9b618def3425ab59724711c0345c5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Rational Kernels: Theory and Algorithms (2004, methodology): “This is always the case when the semiring is k-closed or when M is acyclic (Mohri, 2002), the case of interest in our experiments.”
On trust models and trust evaluation metrics for ad hoc networks (2006, methodology): “As the reader can see in [19], the crucial parameter of the topology is the numb er of paths from the source to the other nodes.”
Prediction, learning, and games (2006, background): “For a general framework of linear-time algorithms to find the shortest path in a directed acyclic graph, we refer to [219].”
Weighted Finite-State Transducer Algorithms. An Overview (2004, methodology): “d[q] is the shortest-distance from q to F [11].”
The image foresting transform: theory, algorithms, and applications (2004, background): “Thealgebraicor“semiring”modelconsidersfixedarc coststhatarecombinedbyanassociativeoperation,that distributesoverthe min function (or, more generally, over a second associative operator which is used to summarize all paths leading to a given node) [28], [29].”
Graph Kernels (2008, background): “From Definition 1 and (3) we find that [A⊕B](i−1)p+k,(j−1)q+l := Aijδkl + δijBkl.”
Better k-best Parsing (2005, methodology): “can be generalized in order to extend the algorithm: first, the formation of the derivation 〈e, 1〉 out of |e| best subderivations (this is a generalization of the binary operator ⊗ in a semiring); second, min1, which chooses the better of two derivations (same as the ⊕ operator in an idempotent semi”
OpenFst: A General and Efficient Weighted Finite-State Transducer Library (2007, methodology): “Table 6 shows operations for sorting a transducer’s transitions or states, for pushing their weights and labels toward the initial or final states, for placing all input ε’s after the non-ε’s and for synchronizing the ε delay [13, 12].”
Speech Recognition with Weighted Finite-State Transducers (2008, methodology): “By this method, the transducer case can be handled as well; see Mohri [1997] for details.”