Trace theory and VLSI design
type: Item
instance of: scholarly article
title: Trace theory and VLSI design
zbMATH Open document ID: 0616.68001
author: Jan L. A. van de Snepscheut
published in: Lecture Notes in Computer Science
publication date: 1985-01-01T00:00:00Z
review text: The book represents a fundamental study devoted to the hardware realization of programs with a high degree of concurrency on VLSI chips. A nice notation based on so-called ''traces'' (formal languages) is proposed for programs that prescribe the cooperation of components arranged in a hierarchical structure. Hierarchical structure assists in bridling the complexity of program design. The components and the way in which they cooperate are defined such that an implementation potentially exhibits a high degree of concurrency. Using this program representation a method of deriving semiconductor chips from programs is proposed. Besides several original ideas developed in order to make the hardware implementation, the work includes valuable results interesting for researchers working in formal language theory and VLSI theory. A beautiful, new algorithm for the minimization of (possible nondeterministic) finite state automata is given, and an approach to solve the problem connected with the notion ''delay-insensivity'' in VLSI theory is presented. I meet the opinion of E. W. Dijkstra that this book is a valuable sample of close connection between mathematical formalism and physical reality, and that it can be interesting for all people working in computer science (and not only for them).
Mathematics Subject Classification ID: 68-02
Mathematics Subject Classification ID: 68N01
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 94C99
zbMATH DE Number: 3999248
zbMATH Keywords: regular languages
zbMATH Keywords: minimization of finite automata
zbMATH Keywords: hardware realization of programs
zbMATH Keywords: concurrency
zbMATH Keywords: VLSI chips
zbMATH Keywords: traces
zbMATH Keywords: formal languages
zbMATH Keywords: complexity of program design
zbMATH Keywords: program representation
zbMATH Keywords: hardware implementation
zbMATH Keywords: delay-insensivity
reviewed by: Juraj Hromkovič
MaRDI profile type: Publication
Recommended article: Q3326832
Recommended article: Q3466683
Recommended article: Q3723713
Recommended article: Q3317032
Recommended article: Q3437690
Recommended article: Q3997643
Recommended article: Q3694700
Recommended article: Q3125430
description: scientific article; zbMATH DE number 3999248