REVIEW 1 major objections 2 minor
Games, mobile processes, and functionss -- alternating, concurrent, and well-bracketed semantics
T0 review · 1 major / 2 minor · reviewed 2026-05-22 · grok-4.3
Pith's one-line read The equivalences induced on lambda terms by the pi-calculus and operational game semantics coincide across their transition systems.
desk verdict This paper defines a concurrent LTS for OGS and output-prioritised LTS for pi, proves operational correspondences, and shows the induced equivalences on lambda terms coincide across variants including complete traces. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Operational correspondence between the labeled transition systems of the pi-calculus encoding and operational game semantics, which ensures matching observable behaviors and coinciding equivalences on lambda terms.
What would settle it
A lambda term where the equivalence under one of the LTSs differs from the equivalence under another, or a reduction sequence in an encoded term whose observable actions fail to match between the new LTSs and the standard ones.
Extended reading notes
Core claim
The central claim is that the equivalences induced on λ-terms by the standard LTS for π, the output-prioritised LTS for π, the concurrent LTS for OGS, the alternating LTS for OGS, and the well-bracketed variant all coincide. Operational correspondence holds between the observable behaviors of the encoding in these LTSs for both call-by-value and call-by-name.
Load-bearing premise
The new concurrent LTS for OGS and the output-prioritised LTS for pi are defined so that their observable behaviors match those of the standard LTSs on the image of the encoding.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper establishes a tight connection between Milner's encoding of the λ-calculus into the Internal π-calculus and operational game semantics (OGS). It proves operational correspondences between various LTSs (standard π with new concurrent OGS; output-prioritised π with standard alternating OGS), shows that the equivalences induced on λ-terms by all these LTSs coincide, and proves that under complete traces the concurrent, alternating, and well-bracketed variants of OGS also coincide. These connections are used to transfer up-to techniques from π to OGS, derive congruence and compositionality results for OGS, and obtain a new behavioural equivalence for full abstraction of the encoding w.r.t. λ-calculus contexts extended with store. Results are illustrated for both call-by-value and call-by-name.
Significance. If the results hold, this work is significant for bridging process calculi and game semantics, enabling transfer of techniques such as up-to methods and yielding a new full-abstraction result for the encoding. The coincidence results under complete traces and the handling of concurrent/alternating/well-bracketed variants provide a unified perspective on behavioural equivalences for λ-terms.
major comments (1)
- [§4] §4 (Operational Correspondence): The central claim that all induced equivalences coincide rests on the operational correspondence between the standard LTSs and the newly introduced concurrent LTS for OGS plus output-prioritised LTS for π. The proofs must explicitly verify that every transition, including internal ones and branching, is preserved exactly on the image of the encoding; without an independent check of this matching, the subsequent equivalence-coincidence arguments and transfer of up-to techniques are at risk of invalidation.
minor comments (2)
- [Title] Title: 'functionss' is a typographical error and should be corrected to 'functions'.
- [Abstract] Abstract: Expand 'LTSs' on first use for readers unfamiliar with the abbreviation.
Simulated Author's Rebuttal
We thank the referee for the careful and constructive review. The positive assessment of the significance of the connections between Milner's encoding and operational game semantics is appreciated. We address the single major comment below and will strengthen the presentation of the proofs as suggested.
read point-by-point responses
-
Referee: [§4] §4 (Operational Correspondence): The central claim that all induced equivalences coincide rests on the operational correspondence between the standard LTSs and the newly introduced concurrent LTS for OGS plus output-prioritised LTS for π. The proofs must explicitly verify that every transition, including internal ones and branching, is preserved exactly on the image of the encoding; without an independent check of this matching, the subsequent equivalence-coincidence arguments and transfer of up-to techniques are at risk of invalidation.
Authors: We agree that explicit verification of transition preservation (including internal τ-moves and branching) on the image of the encoding is essential to support the equivalence-coincidence results and the transfer of up-to techniques. In the submitted manuscript, Section 4 establishes the operational correspondences via a sequence of lemmas proved by structural induction on λ-terms. These lemmas show that the encoding is a strong bisimulation between the respective LTS pairs, with case analysis covering all possible actions, internal communications, and choice points for encoded terms. To make this matching fully transparent and independent as requested, we will revise Section 4 by adding a dedicated summary lemma (with explicit case tables for internal transitions and branching) that isolates the preservation/reflection property on the image of the encoding before proceeding to the equivalence results. This change will be incorporated in the revised version. revision: yes
Circularity Check
No circularity: equivalences shown via independent operational correspondence proofs on standard encodings
full rationale
The paper defines new LTS variants (concurrent for OGS, output-prioritised for π) and proves operational correspondence to standard LTSs on the image of Milner's encoding, then shows induced equivalences on λ-terms coincide. These steps rely on explicit definitions and proofs from prior literature on π-calculus and OGS, without any self-definitional reduction, fitted parameters renamed as predictions, or load-bearing self-citations that collapse the central claims. The derivation is self-contained against external benchmarks consisting of established LTS semantics and trace equivalences.
Assumptions & free parameters
assumptions (2)
- standard math Standard operational semantics and labeled transition systems for the Internal pi-calculus
- standard math Standard definitions of alternating and well-bracketed operational game semantics
Cite this review
Pith. "Pith review of Games, mobile processes, and functionss -- alternating, concurrent, and well-bracketed semantics." pith.science (2026). https://pith.science/paper/2504.18227
@misc{pith2026250418227,
author = {Pith},
title = {Pith review of: Games, mobile processes, and functionss -- alternating, concurrent, and well-bracketed semantics},
year = {2026},
howpublished = {\url{https://pith.science/paper/2504.18227}},
note = {Machine review of arXiv:2504.18227}
}
abstract
We establish a tight connection between two models of the $\lambda$-calculus, namely Milner's encoding into the $\pi$-calculus (precisely, the Internal $\pi$-calculus), and operational game semantics (OGS). We first investigate the operational correspondence between the behaviours of the encoding provided by $\pi$ and OGS. We do so for various LTSs: the standard LTS for $\pi$ and a new `concurrent' LTS for OGS; an `output-prioritised' LTS for $\pi$ and the standard alternating LTS for OGS. We then show that the equivalences induced on $\lambda$-terms by all these LTSs (for $\pi$ and OGS) coincide. We also prove that when equivalence is based on complete traces, the `concurrent' and `alternating' variants of OGS also coincide with the `well-bracketed' variant. These connections allow us to transfer results and techniques between $\pi$ and OGS. In particular: we import up-to techniques from $\pi$ onto OGS; we derive congruence and compositionality results for OGS from those of $\pi$; we transport the notion of complete traces from OGS onto $\pi$, obtaining a new behavioural equivalence that yields a full abstraction result for the encoding of $\lambda$-terms with respect to contexts written in a $\lambda$-calculus extended with store. The study is illustrated for both call-by-value and call-by-name.
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We establish a tight connection between two models of the λ-calculus, namely Milner's encoding into the π-calculus ... and operational game semantics (OGS). We first investigate the operational correspondence between the behaviours of the encoding provided by π and OGS. We do so for various LTSs: the standard LTS for π and a new 'concurrent' LTS for OGS; an 'output-prioritised' LTS for π and the standard alternating LTS for OGS.
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We also prove that when equivalence is based on complete traces, the 'concurrent' and 'alternating' variants of OGS also coincide with the 'well-bracketed' variant.
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reviewed May 22, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.