Order-Enrichment for Categories of Partial Maps

                       Marcelo P. Fiore

                 Department of Computer Science, 
           Laboratory for Foundations of Computer Science,
            University of Edinburgh, The King's Buildings, 
                    Edinburgh EH9 3JZ, Scotland. 
                       <mf@dcs.ed.ac.uk>


                          Synopsis

Motivated by the desire of treating non-termination directly in the
semantics of computation, the notion of approximation between programs
is studied in the context of categories of partial maps. In particular,
contextual approximation and specialisation are considered and shown to
coincide. Moreover, after exhibiting the approximation between total
maps as a primitive notion, from an arbitrary (or axiomatic) 
approximation order on total maps a computationally natural 
approximation order on partial maps is derived. The main technical 
contribution is a characterisation of when this approximation order 
between partial maps is domain-theoretic (in the sense that the 
category of partial maps Cpo-enriches) provided that so is the 
approximation order between total maps.