✳flâneur — a map of the web's best reading

The Algebraic Path Problem

wrbernardoni.github.io · 5,020 words · saved by 1 readers

Many problems are a hidden instance of what is called the Algebraic Path Problem, a method of turning combinatorial problems into solving linear equations over different “number systems”. In this post we give motivating examples of the algebraic path problem, how to solve it, what an idempotent semiring is, and why we would want to talk about idempotent semirings. Consider the following two problems: Both of these problems can be represented as labelled directed graphs, such as in Figure 1 and Figure 2. One problem is the combinatorial problem of searching through potential paths in a network, and the other is finding some sort of steady state in a stochastic process, however we will show that both of these problems are a hidden instance of the Algebraic Path Problem. We can represent a Markov chain as a matrix A 𝐴 , with the entry A ij 𝐴 𝑖 𝑗 being the probability that we transition from state i 𝑖 to state j 𝑗 , i.e.: A ij =P(j∣i,1 step) 𝐴 𝑖 𝑗 = 𝑃 ( 𝑗 ∣ 𝑖 , 1 step )

The Algebraic Path Problem The Algebraic Path Problem | William Bernardoni’s Personal Page The Algebraic Path Problem Why Idempotent Semirings? 31 Oct 2023 Topic: Semiring Geometry Many problems are a hidden instance of what is called the Algebraic Path Problem , a method of turning combinatorial problems into solving linear equations over different “number systems”. In this post we give motivating examples of the algebraic path problem, how to solve it, what an idempotent semiring is, and why we would want to talk about idempotent semirings. Motivating Examples: The Shortest Path Problem and

Explore this link on the map →

related reading