ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
TropicalPaths.h File Reference

Min-cost derivations with the derivations of that cost. More...

#include <limits>
#include <string>
#include <vector>
#include "Regex.h"
Include dependency graph for TropicalPaths.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  semiring::tropical_paths_t
 A cost, and the derivations of that cost. More...
class  semiring::TropicalPaths
 The min-cost-paths semiring over tropical_paths_t. More...

Namespaces

namespace  semiring

Detailed Description

Min-cost derivations with the derivations of that cost.

Pairs \((c, L)\) of a cost \(c \in \mathbb{R} \cup \{+\infty\}\) and a language \(L\) over the labels of the input tuples, the derivations of cost \(c\), written as a regular expression (Regex.h):

  • \((c, L) \oplus (c', L')\) keeps the lower cost, with its derivations, and both languages' union on a tie;
  • \((c, L) \otimes (c', L') = (c + c', L \cdot L')\), the concatenation in the order of the query, so that this semiring does not commute;
  • \(\mathbb{0} = (+\infty, \emptyset)\), \(\mathbb{1} = (0, \{\varepsilon\})\).

On a path query, the value of a tuple is the cost of its shortest paths and those paths. A cycle of positive cost never lies on a shortest path ( \((c, L)^* = \mathbb{1}\)); one of cost zero can be followed any number of times at no cost ( \((0, L)^* = (0, L^*)\)), which a regular expression still writes finitely; one of negative cost makes the cost unbounded, and is refused.

See also
https://provsql.org/lean-docs/Provenance/Semirings/TropicalPaths.html Lean 4 verified m-semiring, whose monus (TropicalPaths.monus, a difference of languages on a tie of costs) this implementation does not compute; with proofs of TropicalPaths.not_commutative, TropicalPaths.not_exclusive, of the stars (TropicalPaths.one_add_mul_one_of_pos, TropicalPaths.one_add_mul_kstar) and of the absence of any solution on a cycle of negative cost (TropicalPaths.no_fixpoint_of_neg).

Definition in file TropicalPaths.h.