Bisimilarity of open terms

AbstractThe standard way of lifting a binary relation, R, from closed terms of an algebra to open terms is to define its closed-instance extension, Rci, which holds for a given pair of open terms if and only if R holds for all their closed instantiations. In this paper, we study alternatives for the case of (strong) bisimulation: we define semantic models for open terms, so-called conditional transition systems, and define bisimulation directly on those models. It turns out that this can be done in at least two different ways, giving rise to formal hypothesis bisimulation ∼fh (due to De Simone) and hypothesis-preserving bisimilarity ∼hp. For open terms, we have (strict) inclusions ∼fh∞∼hp∞∼ci; for closed terms, the three relations coincide. We show that each of these relations is a congruence in the usual sense, and we give an alternative characterisation of ∼hp in terms of non-conditional transitions. Finally, we study the issue of recursive congruence: we give general theorems for the congruence of each of the above variants with respect to the recursion combinator, where, however, the results we achieve for ∼fh and ∼hp hold in a more general setting than the one for ∼ci