Bounded linear logic: A modular approach to polynomial-time computability (Q1193854): Difference between revisions

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.

0 references

zbMATH Keywords

restricted version of linear logic

0 references

complexity specifications

0 references

polynomial-time algorithm

0 references

polynomial-time function

0 references

reviewed by

Cristian S. Calude

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Computational interpretations of linear logic

0 references

0 references

0 references

0 references

0 references

0 references

The structure of multiplicatives

0 references

Q5625124

0 references

Linear logic

0 references

Q3819066

0 references

Π12-logic, Part 1: Dilators

0 references

0 references

0 references

0 references

0 references

Bounded linear logic: A modular approach to polynomial-time computability

0 references

Q3758820

0 references

Relational queries computable in polynomial time

0 references

Opérateurs de mise en mémoire et traduction de Gödel. (Storage operators and Gödel translation)

0 references

0 references

0 references

0 references

0 references

0 references

full work available at URL

https://doi.org/10.1016/0304-3975(92)90386-t

0 references

Identifiers

zbMATH Open document ID

0788.03005

0 references

DOI

10.1016/0304-3975(92)90386-T

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1193854

@@ Property / author @@
-Q1171569
@@ Property / author: Q1171569 / rank @@
-Normal rank
@@ Property / author @@
-Philip J. Scott
@@ Property / author: Philip J. Scott / rank @@
-Normal rank
@@ Property / reviewed by @@
-Cristian S. Calude
@@ Property / reviewed by: Cristian S. Calude / rank @@
-Normal rank
@@ Property / author @@
+Andrej Scedrov
@@ Property / author: Andrej Scedrov / rank @@
+Normal rank
@@ Property / author @@
+Philip J. Scott
@@ Property / author: Philip J. Scott / rank @@
+Normal rank
@@ Property / reviewed by @@
+Cristian S. Calude
@@ Property / reviewed by: Cristian S. Calude / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Computational interpretations of linear logic
@@ Property / cites work: Computational interpretations of linear logic / rank @@
+Normal rank
@@ Property / cites work @@
+Q3800030
@@ Property / cites work: Q3800030 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4133141
@@ Property / cites work: Q4133141 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4035304
@@ Property / cites work: Q4035304 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4035305
@@ Property / cites work: Q4035305 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4769050
@@ Property / cites work: Q4769050 / rank @@
+Normal rank
@@ Property / cites work @@
+The structure of multiplicatives
@@ Property / cites work: The structure of multiplicatives / rank @@
+Normal rank
@@ Property / cites work @@
+Q5625124
@@ Property / cites work: Q5625124 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear logic
@@ Property / cites work: Linear logic / rank @@
+Normal rank
@@ Property / cites work @@
+Q3819066
@@ Property / cites work: Q3819066 / rank @@
+Normal rank
@@ Property / cites work @@
+Π12-logic, Part 1: Dilators
@@ Property / cites work: Π12-logic, Part 1: Dilators / rank @@
+Normal rank
@@ Property / cites work @@
+Q3824307
@@ Property / cites work: Q3824307 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4204146
@@ Property / cites work: Q4204146 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3203017
@@ Property / cites work: Q3203017 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3994895
@@ Property / cites work: Q3994895 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded linear logic: A modular approach to polynomial-time computability
+Normal rank
@@ Property / cites work @@
+Q3758820
@@ Property / cites work: Q3758820 / rank @@
+Normal rank
@@ Property / cites work @@
+Relational queries computable in polynomial time
@@ Property / cites work: Relational queries computable in polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Opérateurs de mise en mémoire et traduction de Gödel. (Storage operators and Gödel translation)
+Normal rank
@@ Property / cites work @@
+Q3204445
@@ Property / cites work: Q3204445 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3325707
@@ Property / cites work: Q3325707 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4712651
@@ Property / cites work: Q4712651 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3698786
@@ Property / cites work: Q3698786 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3707407
@@ Property / cites work: Q3707407 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(92)90386-t
+Normal rank
@@ Property / OpenAlex ID @@
+W1971256104
@@ Property / OpenAlex ID: W1971256104 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q126351278
@@ Property / Wikidata QID: Q126351278 / rank @@
+Normal rank