Publications of the Ptolemy Group
A DENOTATIONAL FRAMEWORK FOR
COMPARING MODELS OF COMPUTATION
by Edward A. Lee and Alberto Sangiovanni-Vincentelli
Memorandum UCB/ERL M97/11,
EECS, University of California, Berkeley, CA, USA 94720.
January 30, 1997
We give a denotational framework (a "meta model") within which certain properties of models of
computation can be understood and 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 computa
tion, 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 firstname.lastname@example.org.