From Branching to Linear Metric Domains (and back)

From Branching to Linear Metric Domains (and back)

Franck van Breugel

In 6th NWPT, pages 444-447


Besides partial orders, also metric spaceshave turned out to be very useful to give semantics to programming languages (see, e.g., the collection of papers of the Amsterdam Concurrency Group. In the literature, one encounters two main classes of metric domains: linear domains and branching domains. Linear domains were already studied by topologists in the early twenties. Branching domains have been introduced by, e.g., De Bakker and Zucker, Golson and Rounds, and the author. The elements of these linear and branching domains are convenient to model-one might even say that they represent-trace equivalenceclasses and bisimulation equivalenceclasses, respectively. The former is a simple observation. The latter has been proved by Van Glabbeek and Rutten.

Linear domains are more abstract than branching domains. Our aim is to show that linear domains can be embedded in branching domains. We focus on the branching domain introduced by De Bakker and Zucker in and the linear domain the elements of which can be viewed as nonempty and compact sets of sequences.

McGill University,School of Computer Science, 3480 University Street, Montreal H3A 2A7, Canada.

Available as PostScript, DVI.

[BRICS symbol] BRICS WWW home page