Authors: Tom Hirschowitz ; Ambroise Lafont

Applicative bisimilarity is a coinductive characterisation of observational equivalence in call-by-name lambda-calculus, introduced by Abramsky (1990).
Howe (1996) gave a direct proof that it is a congruence, and generalised the result to all languages complying with a suitable format. We propose a categorical framework for specifying operational semantics, in which we prove that (an abstract analogue of) applicative bisimilarity is automatically a congruence. Example instances include standard applicative bisimilarity in call-by-name, call-by-value, and call-by-name non-deterministic $\lambda$-calculus, and more generally all languages complying with a variant of Howe's format.

• 03B40 - Combinatory logic and lambda calculus
• 18C50 - Categorical semantics of formal languages
• 68N18 - Functional programming and lambda calculus
• 68Q55 - Semantics in the theory of computing