The complexity of interaction

DOI10.1145/2837614.2837646zbMATH Open1347.68052arXiv1511.01838OpenAlexW2258276823WikidataQ130974876 ScholiaQ130974876MaRDI QIDQ2828261FDOQ2828261

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)

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.

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

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

zbMATH Keywords

linear logictime boundsprogram analysisinteraction netsparallel reductionssequential reductionsspace bounds

Mathematics Subject Classification ID

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

Cited In (2)

• Types for complexity of parallel computation in pi-calculus
• Title not available (Why is that?)

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)