Main Menu/
Search/
Help
Publications of the Ptolemy Group
A FRAMEWORK FOR
COMPARING MODELS OF COMPUTATION
by Edward A. Lee and Alberto Sangiovanni-Vincentelli
Accepted by IEEE Transactions on CAD
Revised from
Memorandum UCB/ERL M97/11,
EECS, University of California, Berkeley, CA, USA 94720,
January 30, 1997
September 27, 1998
![[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 (a "meta model") within which certain
properties of models of computation can be compared. It describes
concurrent processes in general terms as sets of possible behaviors. A
process is determinate if given the constraints imposed by the inputs
there are exactly one or exactly zero behaviors. Compositions of
processes are processes with behaviors in the intersection of the
behaviors of the component processes. The interaction between processes
is through signals, which are collections of events. 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 processes have
only synchronous signals as behaviors. Strict causality (in timed tag
systems) and continuity (in untimed tag 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, Petri nets, and discrete-event
systems.
Send comments to Edward A. Lee at eal@eecs.berkeley.edu.