From truth to computability. I.

DOI10.1016/J.TCS.2006.03.014zbMATH Open1094.03019DBLPjournals/tcs/Japaridze06arXivcs/0407054OpenAlexW1985872645WikidataQ56768690 ScholiaQ56768690MaRDI QIDQ2500484FDOQ2500484

Giorgi Japaridze

Publication date: 16 August 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The recently initiated approach called computability logic is a formal theory of interactive computation. See a comprehensive online source on the subject at http://www.cis.upenn.edu/~giorgi/cl.html . The present paper contains a soundness and completeness proof for the deductive system CL3 which axiomatizes the most basic first-order fragment of computability logic called the finite-depth, elementary-base fragment. Among the potential application areas for this result are the theory of interactive computation, constructive applied theories, knowledgebase systems, systems for resource-bound planning and action. This paper is self-contained as it reintroduces all relevant definitions as well as main motivations.

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

Recommendations

• Propositional computability logic I
• From truth to computability. II.
• Computability logic: giving Caesar what belongs to Caesar
• Introduction to computability logic
• Computability logic: a formal theory of interaction

zbMATH Keywords

computability logicgame semanticsinteractive computationlinear logicknowledge basesconstructive logics

Mathematics Subject Classification ID

Applications of game theory (91A80) Knowledge representation (68T30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) 2-person games (91A05) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47) Logic in artificial intelligence (68T27) Logic in computer science (03B70) Metamathematics of constructive systems (03F50) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Cites Work

• Title not available (Why is that?)
• Introduction to computability logic
• Propositional computability logic I
• Linear logic
• Title not available (Why is that?)
• Games in Dynamic-Epistemic Logic
• A game semantics for linear logic
• Games and full completeness for multiplicative linear logic
• Title not available (Why is that?)
• Computability Logic: A Formal Theory of Interaction
• Title not available (Why is that?)
• A constructive game semantics for the language of linear logic
• The propositional logic of elementary tasks

Cited In (16)

• A PSPACE-complete first-order fragment of computability logic
• Intuitionistic computability logic
• Separating the basic logics of the basic recurrences
• Introduction to clarithmetic. I
• Toggling operators in computability logic
• Many concepts and two logics of algorithmic reduction
• Sequential operators in computability logic
• A new face of the branching recurrence of computability logic
• Introduction to 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
• The taming of recurrences in computability logic through cirquent calculus. II
• The taming of recurrences in computability logic through cirquent calculus. I
• Towards applied theories based on computability logic
• A propositional cirquent calculus for computability logic.

This page was built for publication: From truth to computability. I.

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