TCS Journal 2026 Journal Article
A unifying logical foundation for initial algebra semantics and induction
- Xiaohong Chen
- Dorel Lucanu
- Grigore Roşu
Initial algebra semantics provides a generic and principled framework to study induction. In this paper, we give a complete formalization of ini- tial algebra semantics and inductive reasoning using matching logic—a small and unifying logic for formal semantics of programming languages. Specifi- cally, we define initial algebra semantics as matching logic theories and derive induction/iteration/primitive-recursion principles as formal theorems within matching logic, using its proof system. This way, we obtain, for the first time, a rigorous logical foundation for general initial algebra semantics and induc- tion, both proof-theoretically and model-theoretically. As a bonus, matching logic admits the smallest known proof checker for a logic supporting inductive proofs, of only 240 lines of code.