Models of Computation: Exploring the Power of ComputingThis text focuses on finite problems and emphasizes concrete models of machines and programming styles. Using problems defined over infinite domains and abstract machine models as models, emphasis is given to concrete problems of the kind found in algorithms textbooks, as well as machine models related to current technology. The book integrates the theme of parallelism throughout the book (for example, circuits are presented as parallel machines) and studies the exchanges between space, time and other resources on a variety of machine models. |
Contents
The Role of Theory in Computer Science | 3 |
Logic Circuits | 35 |
Machines with Memory | 91 |
Copyright | |
14 other sections not shown
Common terms and phrases
accepts array binary number bits Boolean function branching program cells chip clause column construct contains context-free convolution decision problems defined definition denoted depth derive deterministic DFSM edges equivalence fan-in FFT graph finite-state machine function f gates grammar hypercube I/O operations induction inequality input string input variables instance integer L₁ language least Lemma length linear log-space log₂ logic circuit lower bound M₁ matrix multiplication monotone circuit n x n n-tuple next-state NFSM non-terminal nondeterministic nondeterministic Turing machine NP-complete O(log output parallel path pebble game pebbling strategy planar circuit polynomial PRAM problem processors Proof PSPACE pushdown automaton random-access memory realized recursive red pebbles regular expressions regular language result satisfies the following Section simulated sorting space straight-line program systolic array tape Theorem Turing machine upper bound vector vertex VLSI x₁