Polynomial time in untyped elementary linear logic
Copyright policy )Polynomial time in untyped elementary linear logic
Abstract We show how to represent polynomial time computation in an untyped version of proof-nets for elementary linear logic. This follows previous work by P. Baillot but which was developed in a typed and affine setting. We describe how these two properties can be adapted.
Elementary Linear Logic, Strong Normalization, Implicit Computational Complexity, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Polynomial Time Computation, [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], Proof Nets
Elementary Linear Logic, Strong Normalization, Implicit Computational Complexity, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Polynomial Time Computation, [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], Proof Nets
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!