Documentation

Provenance.PathSum

Linear recursions over a semiring, read path by path #

A set recursion whose body reads its recursive relation once is linear: its round function is X ↦ ε(B ⊎ X ⊳ G), where X ⊳ G sends a row (u, a) to the rows of G u, each annotated by a times its own annotation, and ε sums the annotations of the copies of a tuple. Its k-th iterate is therefore ε of the sum of the first k rounds B, B ⊳ G, (B ⊳ G) ⊳ G, … (iterate_stepK_eq), and the weight of a tuple in round j is the sum, over the paths of j steps ending at it, of the product of the annotations along the path (y_eq_sum_pathsTo).

The paths give the two facts a bounded simulation of the recursion needs. Over a finite set S of tuples, a path of more than |S| steps repeats a tuple, and the cycle between the two occurrences can be cut or pumped (pw_append_cons):

Either way a recursion that settles does so within |S| rounds (iterate_succ_eq_of_settles). Where ⊗ is ⊕ on non-zero values, as in the lineage semiring (UnionLike), a cycle neither vanishes nor is absorbed, but a path of 2|S| + 1 steps or more has one cycle near each end, and its weight is the sum of the two paths with one of them cut (pw_absorbed), so the weights settle within 2|S| + 1 rounds (wt_trunc_settle_lin). The data part, which annotations do not see, is the same argument over ℕ (exists_lt_ne_zero).

def PathSum.y {α R : Type} [CommSemiring R] (S : Finset α) (b : α → R) (g : α → α → R) :
ℕ → α → R

The weights of the rounds of a linear recursion: b at round 0, then each tuple's weight pushed along g.

Equations
Instances For
    Dependency graph
    def PathSum.x {α R : Type} [CommSemiring R] (S : Finset α) (b : α → R) (g : α → α → R) (M : ℕ) (v : α) :
    R

    The weight of the first M rounds.

    Equations
    Instances For
      Dependency graph
      def PathSum.pw {α R : Type} [CommSemiring R] (b : α → R) (g : α → α → R) :
      List α → R

      The weight of a path, listed from its end back to its start.

      Equations
      Instances For
        Dependency graph
        def PathSum.ep {α R : Type} [CommSemiring R] (g : α → α → R) :
        List α → R

        The product of the edge weights along a list, listed from its end.

        Equations
        Instances For
          Dependency graph
          def PathSum.pathsTo {α : Type} [DecidableEq α] (S : Finset α) :
          ℕ → α → Finset (List α)

          The paths of j steps through S ending at v.

          Equations
          Instances For
            Dependency graph
            def PathSum.pumped {α : Type} (a : α) (l₂ l₃ : List α) :
            ℕ → List α

            The path with its cycle gone round k + 1 times.

            Equations
            Instances For
              Dependency graph

              The semirings where ⊗ is ⊕ on non-zero values, ⊕ being idempotent: the lineage semiring Lin[X], where both are union. A path's weight is then the sum of the weights of its start and of its edges, so a cycle adds edges but repeats nothing.

              Equations
              Instances For
                Dependency graph
                def PathSum.wt {α R : Type} [DecidableEq α] [CommSemiring R] (r : Multiset (α × R)) (u : α) :
                R

                The weight of a tuple in a bag of annotated tuples: the sum of the annotations of its copies.

                Equations
                Instances For
                  Dependency graph
                  def PathSum.supp {α R : Type} [DecidableEq α] (r : Multiset (α × R)) :

                  The tuples a bag holds, whatever their annotations.

                  Equations
                  Instances For
                    Dependency graph
                    def PathSum.dedupK {α R : Type} [DecidableEq α] [CommSemiring R] (r : Multiset (α × R)) :
                    Multiset (α × R)

                    Duplicate elimination: one copy of each tuple, annotated by its weight – and no δ.

                    Equations
                    Instances For
                      Dependency graph
                      def PathSum.lin {α R : Type} [CommSemiring R] {ω : Type} (G : α → Multiset (ω × R)) (X : Multiset (α × R)) :
                      Multiset (ω × R)

                      A linear round: each row (u, a) of the previous round gives the rows of G u, their annotations multiplied by a.

                      Equations
                      Instances For
                        Dependency graph
                        def PathSum.rounds {α R : Type} [CommSemiring R] (B : Multiset (α × R)) (G : α → Multiset (α × R)) :
                        ℕ → Multiset (α × R)

                        The rounds B, B ⊳ G, (B ⊳ G) ⊳ G, ….

                        Equations
                        Instances For
                          Dependency graph
                          def PathSum.trunc {α R : Type} [CommSemiring R] (B : Multiset (α × R)) (G : α → Multiset (α × R)) (k : ℕ) :
                          Multiset (α × R)

                          The sum of the first k rounds.

                          Equations
                          Instances For
                            Dependency graph
                            def PathSum.stepK {α R : Type} [DecidableEq α] [CommSemiring R] (B : Multiset (α × R)) (G : α → Multiset (α × R)) (X : Multiset (α × R)) :
                            Multiset (α × R)

                            The round function of the set recursion: ε(B ⊎ X ⊳ G).

                            Equations
                            Instances For
                              Dependency graph
                              structure PathSum.Closed {α R : Type} [DecidableEq α] (S : Finset α) (B : Multiset (α × R)) (G : α → Multiset (α × R)) :

                              A set of tuples closed under the rounds.

                              • base : supp B ⊆ S
                              • step (u : α) : u ∈ S → supp (G u) ⊆ S
                              Instances For
                                Dependency graph

                                The semirings where a linear set recursion settles within the size of its tuple set, if at all: the absorptive ones, and those where ⊕ cancels and ⊗ has no zero divisors.

                                Equations
                                Instances For
                                  Dependency graph

                                  The semirings where a linear set recursion's weights settle within twice the size of its tuple set: those of SettlesEarly, and those where ⊗ is ⊕ on non-zero values (UnionLike).

                                  Equations
                                  Instances For
                                    Dependency graph

                                    The successor counter #

                                    The bounded simulation of the set recursion runs the same rounds on pairs of a tuple and a counter: the base is paired with every counter of cs, a round pairs each derived tuple with every counter above the current one, and the annotation is multiplied by 𝟙 where the counter is the least one of a sublist cw, or the successor in cw of the current one, and by 𝟘 elsewhere. Round j then holds the tuples of round j of the recursion, each paired with the counters of rank j or more in cs (SimSpec.supp_rounds), annotated by their weight at the j-th counter of cw and 𝟘 at the others (SimSpec.wt_rounds); it is empty from the number of counters on (SimSpec.rounds_eq_zero); and ε of the sum of its rounds, read on the tuples, has the tuples of the first |cs| rounds of the recursion and the weights of its first |cw| rounds (SimSpec.dedupK_rounds). The two lists differ where some counters are annotated 𝟘: their rows are there, and carry nothing.

                                    def PathSum.firstInd {R : Type} [CommSemiring R] {β : Type} [DecidableEq β] (cs : List β) (c : β) :
                                    R

                                    The indicator of a counter being the first one.

                                    Equations
                                    Instances For
                                      Dependency graph
                                      def PathSum.succInd {R : Type} [CommSemiring R] {β : Type} [DecidableEq β] (cs : List β) (c c' : β) :
                                      R

                                      The indicator of c' being the counter right after c.

                                      Equations
                                      Instances For
                                        Dependency graph
                                        structure PathSum.SimSpec {α R : Type} [DecidableEq α] [CommSemiring R] {β : Type} [DecidableEq β] (lt : β → β → Prop) (cs cw : List β) (B : Multiset (α × R)) (G : α → Multiset (α × R)) (B' : Multiset ((α × β) × R)) (G' : α × β → Multiset ((α × β) × R)) :

                                        The hypotheses the simulation's rounds are read under: the counters cs listed in a strictly increasing order, and a sublist cw of them; the base pairing each tuple of B with every counter, and a round pairing each tuple of G t with every counter above c, the annotations multiplied by the indicators of cw.

                                        Instances For
                                          Dependency graph

                                          A strictly sorted list #

                                          def PathSum.dropCtr {α R β : Type} (p : (α × β) × R) :
                                          α × R

                                          Forgetting the counter.

                                          Equations
                                          Instances For
                                            Dependency graph

                                            The all-chains counter #

                                            Where ⊕ and ⊗ do not add copies – in an absorptive semiring – a simulation need not single out the successor of a counter: a round may pair each derived tuple with every counter above the current one. The base pairs each tuple with every counter, multiplying its weight by bw c, and a round from counter c to c' multiplies by sw c c'. Round j then sums, over the paths of j steps and the chains of j + 1 counters, the path's weight times the chain's (wt_rounds_ge), and never weighs more than the recursion's round (wt_rounds_le). So ε of its rounds is the recursion's value as soon as every path through distinct tuples of non-zero weight is absorbed by the weight of some chain (ChainSpec.dedupK_rounds): a path through a cycle is absorbed by the path with the cycle cut.

                                            structure PathSum.ChainSpec {α R : Type} [DecidableEq α] [CommSemiring R] {β : Type} [DecidableEq β] (lt : β → β → Prop) (cs : List β) (bw : β → R) (sw : β → β → R) (B : Multiset (α × R)) (G : α → Multiset (α × R)) (B' : Multiset ((α × β) × R)) (G' : α × β → Multiset ((α × β) × R)) :

                                            The hypotheses the all-chains simulation's rounds are read under: the counters listed in a strictly increasing order, the base pairing each tuple of B with every counter, its weight multiplied by bw, and a round pairing each tuple of G t with every counter above c, its weight multiplied by sw.

                                            • sorted : List.Pairwise lt cs
                                            • irrefl (c : β) : ¬lt c c
                                            • trans (a b c : β) : lt a b → lt b c → lt a c
                                            • base_wt (t : α) (c : β) : c ∈ cs → wt B' (t, c) = wt B t * bw c
                                            • base_supp (t : α) (c : β) : (t, c) ∈ supp B' ↔ t ∈ supp B ∧ c ∈ cs
                                            • step_wt (t : α) (c : β) : c ∈ cs → ∀ (t' : α), ∀ c' ∈ cs, lt c c' → wt (G' (t, c)) (t', c') = wt (G t) t' * sw c c'
                                            • step_supp (t : α) (c : β) : c ∈ cs → ∀ (t' : α) (c' : β), (t', c') ∈ supp (G' (t, c)) ↔ t' ∈ supp (G t) ∧ c' ∈ cs ∧ lt c c'
                                            Instances For
                                              Dependency graph

                                              The order of an absorptive semiring #

                                              The supports #

                                              The weights #

                                              Weights of the usual constructions #