Stable Production Rule Sets are Deterministic

Papadantonakis, Karl (2003) Stable Production Rule Sets are Deterministic. Technical Report. California Institute of Technology. [CaltechCSTR:2003.003]

Full text available as:

	Postscript - Requires a viewer, such as GhostView
	PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

Production Rule Sets (PRS) are a digital event-based model for CMOS circuits; stable production rule sets are those in which in every execution, every enabled rule remains enabled until it is executed. It has been conjectured that stable production rule sets are determinstic, meaning in particular that they cannot implement arbiters, and that the sequence of values sent on any channel is independent of the execution. In this paper, we prove these facts rigorously, directly from first principles. We also propose improvements to PRS testing tools based on the resulting theory.

EPrint Type:	Monograph (Technical Report)
Uncontrolled Keywords:	asynchronous VLSI stability determinism PRS execution arbitration handshaking
Subjects:	All Records
ID Code:	489
Deposited By:	Karl Papadantonakis
Deposited On:	02 July 2003
Record Number:	CaltechCSTR:2003.003
Official Persistent URL:	http://resolver.caltech.edu/CaltechCSTR:2003.003
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record