BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/nondeterministic-arrows.pdf
       ENTRY:: February 6, 2010
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: A Cartesian Category of Nondeterministic Arrows between Domains
        TYPE:: Technical Report
      AUTHOR:: Stark, Eugene W.
     CONTACT:: Eugene W. Stark, Department of Computer Science,
                   SUNY at Stony Brook, Stony Brook, NY 11794-4400
                   Tel: 631-632-8444 <stark@cs.sunysb.edu>
        DATE:: February 6, 2010
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/nondeterministic-arrows.abstract

ABSTRACT::

We show how a simple intuitive conception of nondeterministic
computation leads to a construction, given a locally ordered
bicategory D having finite bicategorical products
(for example, a bicategory of domains and continuous functions
with extensionally ordered homs),
of a bicategory ND of ``nondeterministic arrows''
that embeds D as a locally full sub-bicategory.
The cartesian product on D extends to a pseudofunctorial
tensor product on ND.
We show that, in case the homs of D are
bounded-complete directed complete partial orders
with composition respecting local directed colimits,
then a nondeterministic arrow in ND is a left adjoint
(i.e. a ``map'') if and only if it is isomorphic to
a strict, sup-preserving arrow of D.
Under the additional assumption that D has local terminal
objects (i.e. each hom has a ``top''), then ND
is a cartesian bicategory in the sense of Carboni, et al.
In addition, we note that the ``trace'' that exists on D
via the fixed point theorem extends in a natural way to ND,
thus pointing the way to the use of ND for defining
the semantics of nondeterministic programming constructs.