Propositional computability logic II

DOI10.1145/1131313.1131319zbMATH Open1367.03057DBLPjournals/tocl/Japaridze06aarXivcs/0406037OpenAlexW4253236060WikidataQ56565714 ScholiaQ56565714MaRDI QIDQ5277751FDOQ5277751

Giorgi Japaridze

Publication date: 12 July 2017

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

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.

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

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 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)

Cited In (14)

• A PSPACE-complete first-order fragment of computability logic
• Propositional computability logic I
• Separating the basic logics of the basic recurrences
• Introduction to clarithmetic. I
• Toggling operators in computability logic
• On abstract resource semantics and computability logic
• Sequential operators in computability logic
• A new face of the branching recurrence of computability logic
• The intuitionistic fragment of computability logic at the propositional level
• From truth to computability. II.
• Build your own clarithmetic I: Setup and completeness
• Elementary complexity and geometry of interaction
• 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)