Trace theory and VLSI design (Q1821550)

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