Compiling path expressions into VLSI circuits

T. S. Anantharaman, E. M. Clarke, M. J. Foster, B. Mishra

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Path expressions were originally proposed by Campbell and Habermann as a mechanism for process synchronization at the monitor level in software. Not unexpectedly, they also provide a useful notation for specifying the behavior of asynchronous circuits. Motivated by this potential application we investigate how to directly translate path expressions into hardware. Our implementation is complicated in the case of multiple path expressions by the need for synchronization on event names that are common to more than one path. Moreover, since events are inherently asynchronous in our model, all of our circuits must be self-timed. Nevertheless, the circuits produced by our construction have area proportional to N-log(N) where N is the total length of the multiple path expression under consideration. This bound holds regardless of the number of individual paths or the degree of synchronization between paths.

Original languageEnglish (US)
Title of host publicationConference Record of the Annual ACM Symposium on Principles of Programming Languages
Number of pages14
ISBN (Print)0897911474, 9780897911474
StatePublished - 1985

Publication series

NameConference Record of the Annual ACM Symposium on Principles of Programming Languages
ISSN (Print)0730-8566

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Compiling path expressions into VLSI circuits'. Together they form a unique fingerprint.

Cite this