On abstract resource semantics and computability logic
type: Item
instance of: scholarly article
title: On abstract resource semantics and computability logic
zbMATH Open document ID: 1202.03041
author: Ilya Mezhirov
author: Nikolai K. Vereshchagin
published in: Journal of Computer and System Sciences
publication date: 2010-07-08T00:00:00Z
review text: The paper consists of two sections, focused on Japaridze's abstract resource semantics and computability logic, respectively. The first section introduces a formal definition of a semantics for the ``logic of resources'' based on the notion of \textit{accomplishable formula}; this semantics coincides with \textit{G. Japaridze}'s semantics defined in [Ann. Pure Appl. Logic 117, No.~1--3, 261--293 (2002; Zbl 1013.03017)] and later extended to the abstract resource semantics. The relation between accomplishable formulae and, firstly, affine logic and, secondly, with intuitionistic propositional logic is presented. The second part of the paper focuses on computability logic, whose semantics is given in terms of the notions of static games and \textit{winnable formula}. The main result of this section is that the notions of accomplishability and winnability coincide. Moreover, a partial answer to a conjecture in [\textit{G. Japaridze}, Ann. Pure Appl. Logic 123, No.~1--3, 1--99 (2003; Zbl 1028.03025)] is given, by proving that uniform winnability coincides with non-uniform winnability; however, the initial conjecture ``computable winnability coincides with uniform computable winnability'' remains open.
reviewed by: Manuel Ojeda-Aciego
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 03F52
zbMATH DE Number: 5731996
zbMATH Keywords: abstract resource semantics
zbMATH Keywords: logic of tasks
zbMATH Keywords: game semantics
zbMATH Keywords: linear logic
zbMATH Keywords: computability logic
zbMATH Keywords: positive fragment of intuitionistic logic
MaRDI profile type: Publication
full work available at URL: j.jcss.2009.10.008
OpenAlex ID: W2072873942
cites work: Degrees of indeterminacy of games
cites work: A game semantics for linear logic
cites work: Q4411816
cites work: Linear logic
cites work: Introduction to computability logic
cites work: Introduction to Cirquent Calculus and Abstract Resource Semantics
cites work: Propositional computability logic II
cites work: The intuitionistic fragment of computability logic at the propositional level
cites work: Sequential operators in computability logic
cites work: Many concepts and two logics of algorithmic reduction
cites work: In the beginning was game semantics
cites work: Q4774021
cites work: On Game Semantics of the Affine and Intuitionistic Logics
cites work: Propositional Calculus and Realizability
DOI: 10.1016/J.JCSS.2009.10.008
Recommended article: Q3495341
Recommended article: Q4720780
Recommended article: Abstract computability and algebraic specification
Recommended article: On the complexity of resource-bounded logics
Recommended article: Introduction to Cirquent Calculus and Abstract Resource Semantics
Recommended article: Q4205440
Recommended article: On computability by logic programs
Recommended article: A computable semantics for general logic programs
Recommended article: Intuitionistic Logic and Computability Theory
description: scientific article; zbMATH DE number 5731996