OPEN MAPS, BEHAVIORAL EQUIVALENCES, AND CONGRUENCES

Spans of open maps have been proposed by Joyal, Nielsen, and Winskel a s a way of adjoining an abstract equivalence, P-bisimilarity, to a cat egory of models of computation M, where P is an arbitrary subcategory of observations. Part of the motivation was to recast and generalise M ilner's well-known strong bisimulation In this categorical setting. An issue left open was the congruence properties of P-bisimilarity. We a ddress the following fundamental question: given a category of models of computation M and a category of observations P, are there any condi tions under which algebraic constructs viewed as functors preserve P-b isimilarity? We define the notion of functors being P-factorisable, sh ow how this ensures that P-bisimilarity is a congruence with respect t o such functors. Guided by the definition of P-factorisability we show how it is possible to parametrise proofs of functors being P-factoris able with respect to the category of observations P, i.e., with respec t to a behavioural equivalence.