# Tropical Modeling of Weighted Transducer Algorithms on Graphs

arXiv: https://arxiv.org/abs/1811.00573 · HTML: https://mlsanity.com/paper/1811.00573/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2018.

## Built on by (most cited first, 1 of 1)

- [Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks](https://mlsanity.com/paper/2306.15157/) (2023)

## Abstract (arXiv)

Weighted Finite State Transducers (WFSTs) are versatile data structures that can model a great number of problems, ranging from Automatic Speech Recognition to DNA sequencing. Traditional computer science algorithms are employed when working with these structures in order to optimise their size, but also the runtime of decoding algorithms. However, these algorithms are not unified under a common framework that would allow for their treatment as a whole. Moreover, the inherent geometrical representation of WFSTs, coupled with the topology-preserving algorithms that operate on them make the structures ideal for tropical analysis. The benefits of such analysis have a twofold nature; first, matrix operations offer a connection to nonlinear vector space and spectral theory, and, second, tropical algebra offers a connection to tropical geometry. In this work we model some of the most frequently used algorithms in WFSTs by using tropical algebra; this provides a theoretical unification and allows us to also analyse aspects of their tropical geometry. Further, we provide insights via numerical examples.