Documentation

Provenance.Semirings.TropicalPaths

The min-cost-paths m-semiring (ProvSQL's sr_tropical_paths) #

A value is ๐Ÿ˜, or a cost c with a language L over the labels of the input tuples โ€“ the least cost of a derivation of a tuple, with every derivation of that cost. sr_tropical_paths (src/semiring/TropicalPaths.h, since 1.13.0) computes in it:

โŠ• is the join of a partial order: the lexicographic order of the costs reversed and the languages by inclusion (TropicalPathsVal.le_iff: (c, L) โ‰ค (c', L') when c' < c, or c = c' and L โІ L'), with ๐Ÿ˜ adjoined at the bottom. That order is the natural order of the semiring, and the monus it determines โ€“ a where a has the lower cost, ๐Ÿ˜ where b has, and the difference of the languages on a tie โ€“ makes the semiring an m-semiring (instSemiringWithMonus). ProvSQL refuses to compute that monus (semiring-no-monus: on a tie it is a difference of languages, which needs automata), so the refusal is a gap of the implementation and not of the algebra, exactly as for sr_regex.

The star ProvSQL implements is verified against the fixpoint equation s = ๐Ÿ™ โŠ• a โŠ— s it solves: for a positive cost the solution is ๐Ÿ™ (one_add_mul_one_of_pos: a cycle of positive cost never lies on a shortest path), for a cost 0 it is (0, Lโˆ—) (one_add_mul_kstar: the cycle can be followed any number of times at no cost), and for a negative cost there is none (no_fixpoint_of_neg: the least cost is unbounded), which is what recursion-cycle-no-value refuses.

The costs are any linearly ordered cancellative additive monoid (โ„ for ProvSQL), the labels any type.

structure TropicalPathsVal (C ฮ› : Type) :

A cost and the derivations of that cost: a value of sr_tropical_paths other than ๐Ÿ˜.

Instances For
    Dependency graph

    The key the values are ordered by: the cost reversed, then the language by inclusion.

    Equations
    Instances For
      Dependency graph
      Dependency graph
      Dependency graph
      Dependency graph
      def TropicalPathsVal.sup {C ฮ› : Type} [LinearOrder C] (p q : TropicalPathsVal C ฮ›) :

      โŠ• on two values: the lower cost wins, a tie merges the languages.

      Equations
      Instances For
        Dependency graph
        theorem TropicalPathsVal.sup_of_lt {C ฮ› : Type} [LinearOrder C] {p q : TropicalPathsVal C ฮ›} (h : p.cost < q.cost) :
        p.sup q = p
        Dependency graph
        theorem TropicalPathsVal.sup_of_gt {C ฮ› : Type} [LinearOrder C] {p q : TropicalPathsVal C ฮ›} (h : q.cost < p.cost) :
        p.sup q = q
        Dependency graph
        theorem TropicalPathsVal.sup_of_eq {C ฮ› : Type} [LinearOrder C] {p q : TropicalPathsVal C ฮ›} (h : p.cost = q.cost) :
        p.sup q = { cost := p.cost, paths := p.paths + q.paths }
        Dependency graph
        @[instance_reducible]
        noncomputable instance TropicalPathsVal.instSemilatticeSup {C ฮ› : Type} [LinearOrder C] :

        โŠ• is the join of the order.

        Equations
        Dependency graph
        structure TropicalPaths (C ฮ› : Type) :

        The min-cost-paths semiring: a value of sr_tropical_paths, with ๐Ÿ˜ at the bottom.

        Instances For
          Dependency graph

          The order's key: โŠฅ for ๐Ÿ˜, the value's key otherwise.

          Equations
          Instances For
            Dependency graph
            Dependency graph
            @[instance_reducible]
            noncomputable instance TropicalPaths.instPartialOrder {C ฮ› : Type} [LinearOrder C] :
            Equations
            Dependency graph
            theorem TropicalPaths.some_le_some {C ฮ› : Type} [LinearOrder C] (p q : TropicalPathsVal C ฮ›) :
            { val := some p } โ‰ค { val := some q } โ†” p โ‰ค q
            Dependency graph
            theorem TropicalPaths.none_le {C ฮ› : Type} [LinearOrder C] (a : TropicalPaths C ฮ›) :
            { val := none } โ‰ค a
            Dependency graph
            theorem TropicalPaths.not_some_le_none {C ฮ› : Type} [LinearOrder C] (p : TropicalPathsVal C ฮ›) :
            ยฌ{ val := some p } โ‰ค { val := none }
            Dependency graph
            noncomputable def TropicalPaths.add {C ฮ› : Type} [LinearOrder C] (a b : TropicalPaths C ฮ›) :

            โŠ•: ๐Ÿ˜ is neutral, two values join.

            Equations
            Instances For
              Dependency graph
              @[instance_reducible]
              noncomputable instance TropicalPaths.instAdd {C ฮ› : Type} [LinearOrder C] :
              Add (TropicalPaths C ฮ›)
              Equations
              Dependency graph
              theorem TropicalPaths.none_add {C ฮ› : Type} [LinearOrder C] (a : TropicalPaths C ฮ›) :
              { val := none } + a = a
              Dependency graph
              theorem TropicalPaths.add_none {C ฮ› : Type} [LinearOrder C] (a : TropicalPaths C ฮ›) :
              a + { val := none } = a
              Dependency graph
              theorem TropicalPaths.some_add_some {C ฮ› : Type} [LinearOrder C] (p q : TropicalPathsVal C ฮ›) :
              { val := some p } + { val := some q } = { val := some (p โŠ” q) }
              Dependency graph
              @[instance_reducible]
              noncomputable instance TropicalPaths.instSemilatticeSup {C ฮ› : Type} [LinearOrder C] :

              โŠ• is the join of the order with ๐Ÿ˜ at the bottom.

              Equations
              Dependency graph
              theorem TropicalPaths.add_eq_sup {C ฮ› : Type} [LinearOrder C] (a b : TropicalPaths C ฮ›) :
              a + b = a โŠ” b
              Dependency graph
              @[instance_reducible]
              instance TropicalPaths.instZero {C ฮ› : Type} :
              Equations
              Dependency graph
              @[instance_reducible]
              instance TropicalPaths.instMul {C ฮ› : Type} [AddCommMonoid C] :
              Mul (TropicalPaths C ฮ›)

              โŠ— concatenates the languages, adding the costs; ๐Ÿ˜ absorbs.

              Equations
              • One or more equations did not get rendered due to their size.
              Dependency graph
              @[instance_reducible]
              instance TropicalPaths.instOne {C ฮ› : Type} [AddCommMonoid C] :
              One (TropicalPaths C ฮ›)
              Equations
              Dependency graph
              theorem TropicalPaths.one_def {C ฮ› : Type} [AddCommMonoid C] :
              1 = { val := some { cost := 0, paths := 1 } }
              Dependency graph
              theorem TropicalPaths.some_mul_some {C ฮ› : Type} [AddCommMonoid C] (p q : TropicalPathsVal C ฮ›) :
              { val := some p } * { val := some q } = { val := some { cost := p.cost + q.cost, paths := p.paths * q.paths } }
              Dependency graph
              theorem TropicalPaths.none_mul {C ฮ› : Type} [AddCommMonoid C] (a : TropicalPaths C ฮ›) :
              { val := none } * a = { val := none }
              Dependency graph
              theorem TropicalPaths.mul_none {C ฮ› : Type} [AddCommMonoid C] (a : TropicalPaths C ฮ›) :
              a * { val := none } = { val := none }
              Dependency graph
              theorem TropicalPaths.some_sup_mul {C ฮ› : Type} [LinearOrder C] [AddCommMonoid C] [IsOrderedCancelAddMonoid C] (p q r : TropicalPathsVal C ฮ›) :
              { val := some (p โŠ” q) } * { val := some r } = { val := some p } * { val := some r } + { val := some q } * { val := some r }

              Distributivity on the right, value by value: the lower cost stays the lower after adding the same cost, and a tie's merged language concatenates as the union of the concatenations.

              Dependency graph
              theorem TropicalPaths.mul_some_sup {C ฮ› : Type} [LinearOrder C] [AddCommMonoid C] [IsOrderedCancelAddMonoid C] (p q r : TropicalPathsVal C ฮ›) :
              { val := some r } * { val := some (p โŠ” q) } = { val := some r } * { val := some p } + { val := some r } * { val := some q }

              And on the left.

              Dependency graph
              @[instance_reducible]
              Equations
              • One or more equations did not get rendered due to their size.
              Dependency graph
              Dependency graph
              Dependency graph
              noncomputable def TropicalPaths.deltaInd {C ฮ› : Type} [AddCommMonoid C] (a : TropicalPaths C ฮ›) :

              ProvSQL's TropicalPaths::delta: the indicator of being non-๐Ÿ˜.

              Equations
              Instances For
                Dependency graph
                Dependency graph
                Dependency graph
                theorem TropicalPaths.natCast_pos {C ฮ› : Type} [LinearOrder C] [AddCommMonoid C] [IsOrderedCancelAddMonoid C] {n : โ„•} (hn : 0 < n) :
                โ†‘n = 1
                Dependency graph
                noncomputable def TropicalPaths.monus {C ฮ› : Type} [LinearOrder C] (a b : TropicalPaths C ฮ›) :

                The monus: a where a has the lower cost, ๐Ÿ˜ where b has, and on a tie the difference of the languages, ๐Ÿ˜ if that is empty.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  Dependency graph
                  theorem TropicalPaths.monus_spec' {C ฮ› : Type} [LinearOrder C] (a b c : TropicalPaths C ฮ›) :
                  Dependency graph
                  @[instance_reducible]

                  The min-cost-paths semiring is an m-semiring.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Dependency graph

                  The star, against the fixpoint equation it solves #