A framework for comparing models of computation

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 1998-12, Vol.17 (12), p.1217-1229
Main Authors: Lee, E.A., Sangiovanni-Vincentelli, A.
Format: Article
Language:English
Subjects:
Applied sciences
Computational modeling
Computer networks
Concurrent computing
Councils
Design. Technologies. Operation analysis. Testing
Discrete event systems
Electronics
Exact sciences and technology
Impedance
Integrated circuits
Mathematical model
National electric code
Petri nets
Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices
Signal processing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0278-0070
1937-4151
DOI:10.1109/43.736561