Open Maps, Behavioural Equivalences, and Congruences
Allan Cheng January 1996 
Abstract:Spans of open maps have been proposed by Joyal, Nielsen, and Winskel as a way of adjoining an abstract equivalence, bisimilarity, to a category of models of computation , where is an arbitrary subcategory of observations. Part of the motivation was to recast and generalise Milner's wellknown strong bisimulation in this categorical setting. An issue left open was the congruence properties of bisimilarity. We address the following fundamental question: given a category of models of computation and a category of observations , are there any conditions under which algebraic constructs viewed as functors preserve bisimilarity? We define the notion of functors being factorisable, show how this ensures that bisimilarity is a congruence with respect to such functors. Guided by the definition of factorisability we show how it is possible to parametrise proofs of functors being factorisable with respect to the category of observations , i.e., with respect to a behavioural equivalence.
Available as PostScript, PDF, DVI.
