[Prev][Next][Index][Thread]
Announcement
The following two technical reports are now available
by anonymous ftp:
J.J.M.M. Rutten
A Calculus of Transition Systems (towards universal coalgebra)
Technical report CS-R9503, CWI Amsterdam, 1995.
Available at ftp.cwi.nl as pub/CWIreports/AP/CS-R9503.ps.Z.
Abstract:
By representing transition systems as coalgebras, the three
main ingredients of their theory:
coalgebra, homomorphism, and bisimulation,
can be seen to be in a precise correspondence
to the basic notions of universal algebra:
Sigma-algebra, homomorphism, and
substitutive relation (or congruence).
In this paper, some standard results from universal
algebra (such as the three isomorphism theorems
and facts on the lattices of subalgebras and congruences)
are reformulated (using the afore mentioned correspondence)
and proved for transition systems.
***************************************************************
J.J.M.M. Rutten
Elements of Generalized Ultrametric Domain Theory
Technical report CS-R9507, CWI Amsterdam, 1995.
Available at ftp.cwi.nl as pub/CWIreports/AP/CS-R9507.ps.Z.
Abstract:
A generalized ultrametric space is
an ordinary ultrametric space in which
the distance need not be symmetric, and where
different elements may have distance 0.
Our interest in generalized ultrametric spaces is
primarily motivated by the following observations:
1. (possibly nondeterministic) transition systems can be
naturally endowed
with a generalized ultrametric that captures their
operational behavior in terms of simulations;
2. the category of generalized ultrametric spaces
contains both the categories of preorders and of
ordinary ultrametric spaces as full subcategories.
A theory of generalized ultrametric spaces is developed
along the lines of the work by Smyth and Plotkin (1982)
and America and Rutten (1989), such that its restriction to
preorders and ordinary ultrametric spaces
yields (more and less) familiar facts.
Our work has in common with
other recent work along the same lines---by Flagg and Kopperman,
and Wagner---that it is directly based on Lawvere's
V-categorical interpretation of metric spaces, and
uses results on quasimetrics by Smyth.
It is different in being far less general, and consequently
a number of new results, specific for generalized ultrametric spaces,
is obtained. In particular, domain equations are solved
by means of metric adjoint pairs, and the notions of
(generalized) totally-boundedness and bifinite (or `SFU')
domain are introduced and characterized.