Cirquent Calculus in a Nutshell

Аннотация

This paper is a brief presentation of cirquent calculus, a novel proof system for resource-conscious logics. As such, it is a refinement of sequent calculus with mechanisms that allow to explicitly account for the possibility of sharing of subexpressions/subresources between different expressions/resources. This is achieved by dealing with circuit-style constructs, termed cirquents, instead of formulas, sequents or other tree-like structures. The approach exhibits greater expressiveness, flexibility and efficiency compared to the more traditional proof-theoretic approaches. The need for substantially new deductive tools that could overcome the limitations of sequent calculus while dealing with resource logics surfaced with the birth of computability logic, a game-semantically conceived logic of computational resources and tasks, acting as a formal theory of computability in the same sense as classical logic is a formal theory of truth.Cirquent calculus offers elegant axiomatizations for certain basic fragments of computability logic that have been shown to be inherently unaxiomatizable in sequent calculus or other traditional systems. The paper provides an iformal account on the main characteristic features of cirquent calculus, motivations for it, semantics, advantages over sequent calculus, as well as how cirquent calculus relates to classical and linear logics. Out of several existing cirquent calculus systems, only the simplest and most basic one, CL5, is presented in full detail.