Lune

LICS2020Top-tier venue

A Cellular Howe Theorem

Peio Borthelle, Tom Hirschowitz, Ambroise Lafont

Abstract

We introduce a categorical framework for operational semantics, in which we define substitution-closed bisimilarity, an abstract analogue of the open extension of Abramsky's applicative bisimilarity. We furthermore prove a congruence theorem for substitution-closed bisimilarity, following Howe's method. We finally demonstrate that the framework covers the call-by-name and call-by-value variants of λ-calculus in big-step style. As an intermediate result, we generalise the standard framework of Fiore et al. for syntax with variable binding to the skew-monoidal case.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Weak Similarity in Higher-Order Mathematical Operational Semantics cites Towards a Higher-Order Mathematical Operational Semantics
  • Higher-Order Behavioural Conformances via Fibrations cites Weak Similarity in Higher-Order Mathematical Operational Semantics
  • Higher-Order Behavioural Conformances via Fibrations cites Towards a Higher-Order Mathematical Operational Semantics
  • Allegories of Symbolic Manipulations cites Weak Similarity in Higher-Order Mathematical Operational Semantics
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. Formal metatheory of second-order abstract syntaxMarcelo Fiore, Dmitrij SzamozvancevPOPL 2022 · 20 citations
  2. Towards a Higher-Order Mathematical Operational SemanticsSergey Goncharov, Stefan Milius, Lutz Schröder, Stelios Tsampas et al.POPL 2023 · 15 citations
  3. Weak Similarity in Higher-Order Mathematical Operational SemanticsHenning Urbat, Stelios Tsampas, Sergey Goncharov, Stefan Milius et al.LICS 2023 · 10 citations
  4. Higher-Order Behavioural Conformances via FibrationsHenning UrbatPOPL 2026
  5. Allegories of Symbolic ManipulationsFrancesco GavazzoLICS 2023

Builds on1

  1. Reduction monads and their signaturesBenedikt Ahrens, André Hirschowitz, Ambroise Lafont, Marco MaggesiPOPL 2020 · 2 citations

Related papers

  1. A Unified Treatment of the Substitution Tensor for Presheaves, Nominal Sets, Renaming Sets, and so onFabian Lenke, Stefan Milius, Henning UrbatLICS 2026
  2. Substructural Abstract Syntax with Variable Binding and Single-Variable SubstitutionMarcelo Fiore, Sanjiv RanchodLICS 2025 · 3 citations
  3. Bialgebraic Reasoning on Higher-order Program EquivalenceSergey Goncharov, Stefan Milius, Stelios Tsampas, Henning UrbatLICS 2024 · 4 citations
  4. The Benefit of Being Non-Lazy in Probabilistic λ-calculus: Applicative Bisimulation is Fully Abstract for Non-Lazy Probabilistic Call-by-NameGianluca Curzi, Michele PaganiLICS 2020 · 1 citation
  5. An Algebraic Approach to Formal System MetatheoryFrancesco GavazzoLICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines