Cirquent calculus

Cirquent calculus is a proof calculus which manipulates graph-style constructs termed cirquents, as opposed to the traditional tree-style objects such as formulas or sequents. Cirquents come in a variety of forms, but they all share one main characteristic feature, making them different from the more traditional objects of syntactic manipulation. This feature is the ability to explicitly account for possible sharing of subcomponents between different components. For instance, it is possible to write an expression where two subexpressions F and E, while neither one is a subexpression of the other, still have a common occurrence of a subexpression G (as opposed to having two different occurrences of G, one in F and one in E).

The approach was introduced by G. Japaridze in^[1] as an alternative proof theory capable of “taming” various nontrivial fragments his computability logic, which had otherwise resisted all axiomatization attempts within the traditional proof-theoretic frameworks.^{[2] [3]}

The basic version of cirquent calculus in^[4] was accompanied with an "abstract resource semantics" and the claim that the latter was an adequate formalization of the resource philosophy traditionally associated with linear logic. Based on that claim and the fact that the semantics induced a logic properly stronger than (affine) linear logic, Japaridze argued that linear logic was incomplete as a logic of resources. Furthermore, he argued that not only the deductive power but also the expressive power of linear logic was weak, for it, unlike cirquent calculus, failed to capture the ubiquitous phenomenon of resource sharing.^[5]

Among the later-found applications of cirquent calculus was the use of it to define a semantics for purely propositional independence-friendly logic.^[6] The corresponding logic was axiomatized by W. Xu.^[7]

Literature

• M.Bauer, “The computational complexity of propositional cirquent calculus”. Logical Methods is Computer Science 11 (2015),

Issue 1, Paper 12, pp. 1–16.

• G.Japaridze, “Introduction to cirquent calculus and abstract resource semantics”. Journal of Logic and Computation 16 (2006), pp. 489–532.
• G.Japaridze, “Cirquent calculus deepened.” Journal of Logic and Computation 18 (2008), pp. 983–1028.
• G.Japaridze, “From formulas to cirquents in computability logic”. Logical Methods in Computer Science 7 (2011), Issue 2 , Paper 1, pp. 1–55.
• G.Japaridze, “The taming of recurrences in computability logic through cirquent calculus, Part I”.Archive for Mathematical Logic 52 (2013), pages 173–212.
• G.Japaridze, “The taming of recurrences in computability logic through cirquent calculus, Part II” Archive for Mathematical Logic 52 (2013), pages 213–259.
• W.Xu and S.Liu, “Soundness and completeness of the cirquent calculus system CL6 for computability logic”. Logic Journal of the IGPL 20 (2012), pp. 317–330.
• W.Xu and S.Liu, “Cirquent calculus system CL8S versus calculus of structures system SKSg for propositional logic”. In: Quantitative Logic and Soft Computing. Guojun Wang, Bin Zhao and Yongming Li, eds. Singapore, World Scientific, 2012, pp. 144–149.
• W.Xu, “A propositional system induced by Japaridze's approach to IF logic”. Logic Journal of the IGPL 22 (2014), pages 982–991.

References

1. G.Japaridze, “Introduction to cirquent calculus and abstract resource semantics”. Journal of Logic and Computation 16 (2006), pp. 489–532.
2. G.Japaridze, “The taming of recurrences in computability logic through cirquent calculus, Part I”.Archive for Mathematical Logic 52 (2013), pages 173-212.
3. G.Japaridze, “The taming of recurrences in computability logic through cirquent calculus, Part II” Archive for Mathematical Logic 52 (2013), pages 213–259.
4. G.Japaridze, "Introduction to cirquent calculus and abstract resource semantics". Journal of Logic and Computation 16 (2006), pp. 489–532.
5. G.Japaridze, “Cirquent calculus deepened.” Journal of Logic and Computation 18 (2008), pp. 983–1028.
6. G.Japaridze, “From formulas to cirquents in computability logic”. Logical Methods is Computer Science 7 (2011), Issue 2 , Paper 1, pp. 1–55.
7. W.Xu, “A propositional system induced by Japaridze's approach to IF logic”. Logic Journal of the IGPL 22 (2014), pages 982–991.