Min-max semiring #
This file defines the min-max semiring MinMax α over a bounded linear order α,
where addition is min and multiplication is max. The natural order is the
reverse of the order on α (so ⊤ is the additive identity and ⊥ the
multiplicative identity). This semiring models security levels or (dually) the fuzzy
semiring.
Which order a line speaks in. The two orders are opposite, and a
statement reads as its own negation if the reader supplies the wrong one:
the semiring's natural order is what the axioms and every statement of
Provenance.SemiringWithMonus use (𝟘 = ⊤ is least), while the
carrier's order on α is what the monus is implemented in
(a ⊖ b = ⊤ where a.val ≥ b.val). The proofs below say .val wherever
they mean the carrier's. Provenance.Semirings.Tropical has the same
reversal, and each file has misled a reader at least once: when a line
looks backwards, check which order it is written in first.
Also defined:
MaxMin α = MinMax (OrderDual α)– the dual semiring withmaxfor addition andminfor multiplicationTVL– three-valued logic{⊥, unknown, ⊤}, an instance ofMaxMin
MinMax α is absorptive and idempotent. The dual MaxMin TVL does not satisfy
left-distributivity of multiplication over monus.
The security/access control semiring is discussed in Green & Tannen, The Semiring Framework for Database Provenance.
References #
The min-max semiring over a bounded linear order: addition is min, multiplication
is max, zero is ⊤ and one is ⊥. The natural order is the reverse of α's order.
- val : α
Instances For
Dependency graph
Equations
- instCoeMinMax = { coe := MinMax.val }
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- instZeroMinMax = { zero := ⊤ }
Dependency graph
Dependency graph
Equations
- instOneMinMax = { one := ⊥ }
Dependency graph
Dependency graph
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
MinMax α is a commutative m-semiring for any bounded linear order α.
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- instCommSemiringWithMonusMinMax = { toSemiringWithMonus := instSemiringWithMonusMinMax, mul_comm := ⋯ }
Dependency graph
Dependency graph
MinMax α is not exclusive as soon as the chain has an element other
than its two bounds: it is absorptive and totally ordered, so
not_exclusive_of_absorptive_of_total applies. Here 𝟘 = ⊤ and 𝟙 = ⊥.
Dependency graph
Dependency graph
Dependency graph
MinMax α has characteristic 0 in the CharP sense whenever α is nontrivial:
it is idempotent, and (0 : MinMax α) = ⟨⊤⟩ differs from (1 : MinMax α) = ⟨⊥⟩
since ⊥ ≠ ⊤ in a nontrivial bounded order.
Dependency graph
Instances For
Dependency graph
Equations
- instCommSemiringMaxMin = { toSemiring := instSemiringWithMonusMinMax.toSemiring, mul_comm := ⋯ }
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- instCommSemiringWithMonusMaxMin = { toSemiringWithMonus := instSemiringWithMonusMaxMin, mul_comm := ⋯ }
Dependency graph
Dependency graph
Three-valued logic {⊥, unknown, ⊤}, used as an instance of MaxMin.
Instances For
Dependency graph
Dependency graph
Equations
- instReprTVL = { reprPrec := instReprTVL.repr }
Dependency graph
Equations
- instReprTVL.repr TVL.bot prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "TVL.bot")).group prec✝
- instReprTVL.repr TVL.unknown prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "TVL.unknown")).group prec✝
- instReprTVL.repr TVL.top prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "TVL.top")).group prec✝
Instances For
Dependency graph
Equations
- instOrdTVL = { compare := instOrdTVL.ord }
Dependency graph
Equations
- instOrdTVL.ord x✝ y✝ = compare x✝.ctorIdx y✝.ctorIdx
Instances For
Dependency graph
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- instOrderBotTVL = { bot := TVL.bot, bot_le := instOrderBotTVL._proof_1 }
Dependency graph
Equations
- instOrderTopTVL = { top := TVL.top, le_top := instOrderTopTVL._proof_1 }
Dependency graph
Equations
Dependency graph
Equations
Dependency graph
Dependency graph
Dependency graph
MaxMin α has characteristic 0 in the CharP sense whenever α is nontrivial:
this lifts the general MinMax instance to the dual order through
MaxMin α = MinMax (OrderDual α). In particular it applies to MaxMin TVL since
TVL is nontrivial.
Dependency graph
Dependency graph
Orientation #
The carrier is α with its order reversed: 𝟘 is α's top and 𝟙
its bottom, ⊕ is α's min and ⊗ its max, and ≤ on MinMax α
is ≥ on α. The point of the reversal is that the semiring order
comes out the right way up – 𝟘 least and 𝟙 greatest, as a
canonically ordered semiring needs – so read in the semiring, ⊕ is
the join, ⊗ the meet, 𝟙 the top and 𝟘 the bottom. A statement
about min-max is therefore true in either telling; only the α-values
change places, which is worth saying because 𝟙 = ⟨⊥⟩ reads as
“𝟙 is the bottom” and means the opposite.