Subatomic Proof Systems
Andrea Aler Tubella, Alessio Guglielmi · ACM Transactions on Computational Logic · 2018
This article presents the first in a series of results that allow us to develop a theory providing finer control over the complexity of normalization, and in particular of cut elimination. By considering atoms as self-dual noncommutative connectives, we are able to classify a vast class of inference rules in a uniform and very simple way. This allows us to define simple conditions that are easily verifiable and that ensure normalization and cut elimination by way of a general theorem. In this article, we define and consider splittable systems , which essentially make up a large class of linear logics, including Multiplicative Linear Logic and BV, and we prove for them a splitting theorem , guaranteeing cut elimination and other admissibility results as corollaries. In articles to follow, we will extend this result to nonlinear logics. The final outcome will be a comprehensive theory giving a uniform treatment for most existing logics and providing a blueprint for the design of future proof systems.