2017/02/20 by Anton Salikhmetov, Salikhmetov, Anton
Computer Science · #Distributed systems and fault tolerance #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1702.06092
openalex publication_date 2017/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Reducing interaction nets without any specific strategy benefits from constant time per step. On the other hand, a canonical reduction step for weak reduction to interface normal form is linear by depth of terms. In this paper, we refine the weak interaction calculus to reveal the actual cost of its reduction. As a result, we obtain a notion of needed reduction that can be implemented in constant time per step without allowing any free ports and without sacrificing parallelism.