Propositional computability logic II

DOI10.1145/1131313.1131319MaRDI QIDQ5277751zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Giorgi Japaridze

Publication date 12 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0406037

zbMATH Keywords

computability logicgame semanticslinear logiccomputational resourcesinteractive algorithms

Mathematics Subject Classification ID

Applications of game theory (91A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Logic in computer science (03B70) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Abstract: Computability logic is a formal theory of computational tasks and resources. Its formulas represent interactive computational problems, logical operators stand for operations on computational problems, and validity of a formula is understood as being a scheme of problems that always have algorithmic solutions. A comprehensive online source on the subject is available at http://www.cis.upenn.edu/~giorgi/cl.html . The earlier article "Propositional computability logic I" proved soundness and completeness for the (in a sense) minimal nontrivial fragment CL1 of computability logic. The present paper extends that result to the significantly more expressive propositional system CL2. What makes CL2 more expressive than CL1 is the presence of two sorts of atoms in its language: elementary atoms, representing elementary computational problems (i.e. predicates), and general atoms, representing arbitrary computational problems. CL2 conservatively extends CL1, with the latter being nothing but the general-atom-free fragment of the former.

Recommendations

• Propositional computability logic I
• scientific article; zbMATH DE number 1045389
• scientific article; zbMATH DE number 1354108
• scientific article; zbMATH DE number 6680837
• On computability by logic programs
• The intuitionistic fragment of computability logic at the propositional level
• Intuitionistic computability logic
• scientific article; zbMATH DE number 3995647
• Introduction to computability logic
• scientific article; zbMATH DE number 4164188

Cited in

(16)

• From truth to computability. II.
• Elementary complexity and geometry of interaction
• A PSPACE-complete first-order fragment of computability logic
• From formulas to cirquents in computability logic
• Separating the basic logics of the basic recurrences
• Soundness and completeness of the cirquent calculus system CL6 for computability logic
• On abstract resource semantics and computability logic
• Propositional computability logic I
• Sequential operators in computability logic
• Build your own clarithmetic. I: Setup and completeness
• A new face of the branching recurrence of computability logic
• Introduction to clarithmetic. I
• The intuitionistic fragment of computability logic at the propositional level
• Toggling operators in computability logic
• Towards applied theories based on computability logic
• A propositional cirquent calculus for computability logic.

This page was built for publication: Propositional computability logic II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5277751)