The complexity of interaction

DOI10.1145/2837614.2837646MaRDI QIDQ2828261zbMATH OpenOpenAlexWikidataFDO

Authors Stéphane Gimenez, Georg Moser

Publication date 24 October 2016

Published in Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Search for Journal in Brave)

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

zbMATH Keywords

interaction netslinear logicparallel reductionsprogram analysissequential reductionsspace boundstime bounds

Mathematics Subject Classification ID

Proof-theoretic aspects of linear logic and other substructural logics (03F52) Functional programming and lambda calculus (68N18) Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: In this paper, we analyze the complexity of functional programs written in the interaction-net computation model, an asynchronous, parallel and confluent model that generalizes linear-logic proof nets. Employing user-defined sized and scheduled types, we certify concrete time, space and space-time complexity bounds for both sequential and parallel reductions of interaction-net programs by suitably assigning complexity potentials to typed nodes. The relevance of this approach is illustrated on archetypal programming examples. The provided analysis is precise, compositional and is, in theory, not restricted to particular complexity classes.

Recommendations

• The structure of interaction
• Types for complexity of parallel computation in pi-calculus
• Type assignment and termination of interaction nets
• Computation by interaction for space-bounded functional programming
• Complexity analysis in presence of control operators and higher-order functions

Cited in

(2)

• Types for complexity of parallel computation in pi-calculus
• scientific article; zbMATH DE number 1755135 (Why is no real title available?)

This page was built for publication: The complexity of interaction

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