Bounded linear logic: A modular approach to polynomial-time computability
type: Item
instance of: scholarly article
title: Bounded linear logic: A modular approach to polynomial-time computability
zbMATH Open document ID: 0788.03005
DOI: 10.1016/0304-3975(92)90386-T
author: Jean-Yves Girard
author: Andre Scedrov
author: Philip Scott
published in: Theoretical Computer Science
publication date: 1992-09-27T00:00:00Z
review text: The paper uses a restricted version of linear logic [each use of an exponential connective is bounded from advance] in order to produce complexity specifications. Any functional term of appropriate type encodes a polynomial-time algorithm and -- most intriguing -- any polynomial-time function can be obtained in this way. This is a splendid piece of theory motivated by fairly practical questions.
Mathematics Subject Classification ID: 03B20
Mathematics Subject Classification ID: 03F03
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 65298
zbMATH Keywords: restricted version of linear logic
zbMATH Keywords: complexity specifications
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: polynomial-time function
reviewed by: Cristian S. Calude
MaRDI profile type: Publication
cites work: Computational interpretations of linear logic
cites work: Q3800030
cites work: Q4133141
cites work: Q4035304
cites work: Q4035305
cites work: Q4769050
cites work: The structure of multiplicatives
cites work: Q5625124
cites work: Linear logic
cites work: Q3819066
cites work: Π12-logic, Part 1: Dilators
cites work: Q3824307
cites work: Q4204146
cites work: Q3203017
cites work: Q3994895
cites work: Q3758820
cites work: Relational queries computable in polynomial time
cites work: Opérateurs de mise en mémoire et traduction de Gödel. (Storage operators and Gödel translation)
cites work: Q3204445
cites work: Q3325707
cites work: Q4712651
cites work: Q3698786
cites work: Q3707407
full work available at URL: 0304-3975(92)90386-t
OpenAlex ID: W1971256104
Wikidata QID: Q126351278
description: scientific article; zbMATH DE number 65298