A Caltech Library Service

Space-time Algorithms: Semantics and Methodology


Chen, Marina Chien-mei (1983) Space-time Algorithms: Semantics and Methodology. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/bfpj-t811.


A methodology for specifying concurrent systems is presented. A model of computation for concurrent systems is presented first. The syntax and semantics of the language CRYSTAL are introduced. The specification of a system is called a space-time algorithm since space and time are explicit parameters in the description. Fixed-point semantics is used for abstracting the behavior of a system from its implementation. The consistency between an implementation and its description can therefore be ensured using this method. Formal semantics for an arbitrary transistor network is given. An "interpreter" for space-time algorithms -- a hierarchical simulator -- for VLSI systems is presented. The framework can be viewed as a concurrent programming notation when describing communicating processes and as a hardware description notation when specifying integrated circuits.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Computer Science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Mead, Carver
Thesis Committee:
  • Johnson, William Lewis (chair)
  • Kajiya, James Thomas
  • Kechris, Alexander S.
  • Martin, Alain J.
  • Mead, Carver
Defense Date:5 May 1983
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)3771
Office of Naval Research (ONR)N00014-79-C-0597
Record Number:CaltechETD:etd-08312006-094203
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3296
Deposited By: Imported from ETD-db
Deposited On:15 Sep 2006
Last Modified:16 Apr 2021 22:28

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page