The parallel versus branching recurrences in computability logic

Abstract

This paper shows that the basic logic induced by the parallel recurrence of Computability Logic is a proper superset of the basic logic induced by the branching recurrence. The latter is known to be precisely captured by the cirquent calculus system CL15, conjectured by Japaridze to remain sound---but not complete---with parallel recurrence instead of branching recurrence. The present result is obtained by positively verifying that conjecture. A secondary result of the paper is showing that parallel recurrence is strictly weaker than branching recurrence in the sense that, while the latter logically implies the former, vice versa does not hold.

14 pages

References in corpus (10)

• Introduction to Cirquent Calculus and Abstract Resource Semantics
• Cirquent calculus deepened
• Many concepts and two logics of algorithmic reduction
• The taming of recurrences in computability logic through cirquent calculus, Part I
• The logic of interactive Turing reduction
• From formulas to cirquents in computability logic
• In the beginning was game semantics
• A new face of the branching recurrence of computability logic
• The taming of recurrences in computability logic through cirquent calculus, Part II
• Separating the basic logics of the basic recurrences

Cited by in corpus (7)

• On the system CL12 of computability logic
• The Computational Complexity of Propositional Cirquent Calculus
• Build your own clarithmetic I: Setup and completeness
• Elementary-base cirquent calculus I: Parallel and choice connectives
• A propositional system induced by Japaridze's approach to IF logic
• A cirquent calculus system with clustering and ranking
• Implementing program extraction from CL1-proofs