Main Menu/Search/Help
PUBLICATIONS of the DSP DESIGN GROUP and the PTOLEMY PROJECT
The Tagged Signal Model -
A Preliminary Version of a Denotational Framework for
Comparing Models of Computation
by Edward A. Lee and Alberto Sangiovanni-Vincentelli
Memorandum UCB/ERL M96/33,
EECS, University of California, Berkeley, CA, USA 94720.
![[PS]](http://ptolemy.eecs.berkeley.edu/papers/icons/Postscript.gif)
![[PDF]](http://ptolemy.eecs.berkeley.edu/papers/icons/PDF.gif)
ABSTRACT
We give a denotational framework that describes concurrent processes
in very general terms as sets of possible behaviors. Compositions of
processes are given as intersections of their behaviors. The
interaction between processes is through signals, which are
collections of events. A system is determinate if given the
constraints imposed by the inputs there are exactly one or exactly
zero behaviors. Each event is a value-tag pair, where the tags can
come from a partially ordered or totally ordered set. Timed models are
where the set of tags is totally ordered. Synchronous events share the
same tag, and synchronous signals contain events with the same set of
tags. Synchronous systems contain synchronous signals. Strict
causality (in timed systems) and continuity (in untimed systems)
ensure determinacy under certain technical conditions. The framework
is used to compare certain essential features of various models of
computation, including Kahn process networks, dataflow, sequential
processes, concurrent sequential processes with rendezvous, and
discrete-event systems.
Send comments to Edward A. Lee at eal@eecs.berkeley.edu.