The taming of recurrences in computability logic through cirquent calculus, Part I

Abstract

This paper constructs a cirquent calculus system and proves its soundness and completeness with respect to the semantics of computability logic (see http://www.cis.upenn.edu/~giorgi/cl.html). The logical vocabulary of the system consists of negation, parallel conjunction, parallel disjunction, branching recurrence, and branching corecurrence. The article is published in two parts, with (the present) Part I containing preliminaries and a soundness proof, and (the forthcoming) Part II containing a completeness proof.

References in corpus (21)

• Sequential operators in computability logic
• Introduction to Cirquent Calculus and Abstract Resource Semantics
• Propositional computability logic I
• Cirquent calculus deepened
• From truth to computability I
• The intuitionistic fragment of computability logic at the propositional level
• Propositional Computability Logic II
• Intuitionistic computability logic
• Many concepts and two logics of algorithmic reduction
• From truth to computability II
• The taming of recurrences in computability logic through cirquent calculus, Part I
• Toggling operators in computability logic
• The logic of interactive Turing reduction
• From formulas to cirquents in computability logic
• Introduction to clarithmetic II
• Towards applied theories based on computability logic
• In the beginning was game semantics
• A logical basis for constructive systems
• A new face of the branching recurrence of computability logic
• Introduction to clarithmetic I
• Separating the basic logics of the basic recurrences

Cited by in corpus (11)

• The taming of recurrences in computability logic through cirquent calculus, Part I
• The parallel versus branching recurrences in computability logic
• On the system CL12 of computability logic
• The taming of recurrences in computability logic through cirquent calculus, Part II
• The Computational Complexity of Propositional Cirquent Calculus
• Build your own clarithmetic I: Setup and completeness
• Elementary-base cirquent calculus I: Parallel and choice connectives
• On the toggling-branching recurrence of Computability Logic
• Implementing program extraction from CL1-proofs
• A propositional system induced by Japaridze's approach to IF logic
• A cirquent calculus system with clustering and ranking