This free book presents a large number of recent research results previously unavailable in book form. Initially deals with the wee-known computation models, and goes on to special types of circuits, parallel computers, and branching programs. Includes basic theory as well recent research findings. Each chapter includes exercises.
Book Description
Research on the complexity of Boolean functions in non-uniform computation models is now part of one of the most interesting and important areas in theoretical computer science. It has a direct relevance to practical problems in the computer aided design of digital circuits. In this book Professor Dr. Wegener presents a large number of recent research results for the first time.
Table of Contents
- Introduction to the theory of Boolean functions and circuits
- The minimization of Boolean functions
- The design of efficient circuits for some fundamental functions
- Asymptotic results and universal circuits
- Lower bounds on circuit complexity
- Relations between circuit size, formula size, and depth
- Formula size
- Circuits and other non uniform computation methods vs. Turing machines and other uniform computation models
- Hierarchie, mass production and reductions
- Bounded-depth circuits
- Synchronous, planar, and probabilistic circuits
- PRAMs and WRAMs: Parallel random access machines
- Pranching Programs