Semiring Semantics

on YouTube ↗01h 06m

" summary

Semiring semantics evaluates formulas in commutative semirings so truth becomes annotated values; negation is handled by translating to negation normal form and using dual indeterminate polynomials modulo x·x̄=0, yielding a universal homomorphism property and polynomials that enumerate proof trees and evaluation strategies. For fixed points the theory requires absorptive fully continuous semirings, which give least/greatest fixed points and a sum‑of‑strategies theorem for Büchi games. Results: provenance, repairs and edge‑profiles follow; many classical theorems generalize only for restricted semirings, and counting strategies can be exponential.

AI-written summary · about

" chapters (8)

1. 0:00Workshop introduction
2. 3:36Semiring semantics basics
3. 13:48Limitations of positive queries
4. 17:44Handling negation
5. 32:02Extending beyond first-order logic
6. 44:32Strategy analysis in infinite games
7. 53:37Generalizing classical logic results
8. 1:03:13Future directions

" related talks

• 01h 02mAlgebraic Structures in Logic and Query Evaluation 3Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 06mAlgebraic Structures in Logic and Query Evaluation 1Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 05mRelational ProgrammingRemy Wang · 9th Annual Simons Institute Industry Day
• 18mParikh's Theorem Made SymbolicAnthony W. Lin, Matthew Hague, Artur Jez · POPL 2024
• 24mWhen Less Is More: Consequence-Finding in a Weak Theory of ArithmeticZachary Kincaid, Shaowei Zhu, Nicolas Koh · POPL 2023
• 36mOptimizing Relational Programs IIRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023