Skip to Main content Skip to Navigation
Conference papers

A Complete Normal-Form Bisimilarity for State

Abstract : We present a sound and complete bisimilarity for an untyped $λ-calculus$ with higher-order local references. Our relation compares values by applying them to a fresh variable, like normal-form bisimilarity, and it uses environments to account for the evolving store. We achieve completeness by a careful treatment of evaluation contexts comprising open stuck terms. This work improves over Støvring and Lassen's incomplete environment-based normal-form bisimilarity for the $λρ-calculus$, and confirms, in relatively elementary terms, Jaber and Tabareau's result , that the state construct is discriminative enough to be characterized with a bisimilarity without any quantification over testing arguments.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Sergueï Lenglet Connect in order to contact the contributor
Submitted on : Monday, April 1, 2019 - 1:59:36 PM
Last modification on : Wednesday, November 3, 2021 - 7:57:44 AM
Long-term archiving on: : Tuesday, July 2, 2019 - 1:54:53 PM


Files produced by the author(s)




Dariusz Biernacki, Sergueï Lenglet, Piotr Polesiuk. A Complete Normal-Form Bisimilarity for State. FoSSaCS, Apr 2019, Prague, Czech Republic. ⟨10.1007/978-3-030-17127-8_6⟩. ⟨hal-02086532⟩



Record views


Files downloads