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):
- in an absorptive semiring (
𝟙 ⊕ a = 𝟙), a path through a cycle is absorbed by the path with the cycle cut, so the rounds past|S|add nothing (x_add_y_of_absorptive); - in a semiring with no zero divisors, a path of non-zero weight
through a cycle pumps into paths of every larger length, so the rounds
past
|S|vanish wherever some round does (y_eq_zero_of_eq_zero).
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).
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
The weight of the first M rounds.
Equations
- PathSum.x S b g M v = ∑ j ∈ Finset.range M, PathSum.y S b g j v
Instances For
Dependency graph
The weight of a path, listed from its end back to its start.
Equations
- PathSum.pw b g [] = 0
- PathSum.pw b g [u] = b u
- PathSum.pw b g (v :: u :: l) = g u v * PathSum.pw b g (u :: l)
Instances For
Dependency graph
The product of the edge weights along a list, listed from its end.
Equations
- PathSum.ep g [] = 1
- PathSum.ep g [u] = 1
- PathSum.ep g (v :: u :: l) = g u v * PathSum.ep g (u :: l)
Instances For
Dependency graph
The paths of j steps through S ending at v.
Equations
Instances For
Dependency graph
The path with its cycle gone round k + 1 times.
Equations
- PathSum.pumped a l₂ l₃ 0 = a :: l₃
- PathSum.pumped a l₂ l₃ j.succ = a :: (l₂ ++ PathSum.pumped a l₂ l₃ j)
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
The weight of a tuple in a bag of annotated tuples: the sum of the annotations of its copies.
Equations
- PathSum.wt r u = (Multiset.map Prod.snd (Multiset.filter (fun (p : α × R) => p.1 = u) r)).sum
Instances For
Dependency graph
The tuples a bag holds, whatever their annotations.
Equations
Instances For
Dependency graph
Duplicate elimination: one copy of each tuple, annotated by its
weight – and no δ.
Equations
- PathSum.dedupK r = Multiset.map (fun (u : α) => (u, PathSum.wt r u)) (Multiset.map Prod.fst r).dedup
Instances For
Dependency graph
A linear round: each row (u, a) of the previous round gives the
rows of G u, their annotations multiplied by a.
Equations
- PathSum.lin G X = X.bind fun (p : α × R) => Multiset.map (fun (q : ω × R) => (q.1, p.2 * q.2)) (G p.1)
Instances For
Dependency graph
The rounds B, B ⊳ G, (B ⊳ G) ⊳ G, ….
Equations
- PathSum.rounds B G 0 = B
- PathSum.rounds B G j.succ = PathSum.lin G (PathSum.rounds B G j)
Instances For
Dependency graph
The sum of the first k rounds.
Equations
- PathSum.trunc B G k = ∑ j ∈ Finset.range k, PathSum.rounds B G j
Instances For
Dependency graph
The round function of the set recursion: ε(B ⊎ X ⊳ G).
Equations
- PathSum.stepK B G X = PathSum.dedupK (B + PathSum.lin G X)
Instances For
Dependency graph
A set of tuples closed under the rounds.
- base : supp B ⊆ 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
- PathSum.SettlesEarly R = ((∀ (a : R), 1 + a = 1) ∨ (∀ (a b : R), a + b = a → b = 0) ∧ NoZeroDivisors R)
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.
The indicator of a counter being the first one.
Instances For
Dependency graph
The indicator of c' being the counter right after c.
Instances For
Dependency graph
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.
- sorted : List.Pairwise lt cs
- trans (a b c : β) : lt a b → lt b c → lt a c
- wsorted : List.Pairwise lt cw
Instances For
Dependency graph
A strictly sorted list #
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.
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
- trans (a b c : β) : lt a b → lt b c → lt a c