International Thompson Computer Press. April 1997.

Paperback, xv+716 pages, 214 figures/tables, ISBN: 1-85032-243-0

Price: US $35.95, UK £25.95, Canada $50.95

About the book

An innovative, synthetizing, much broader than usual, precise but not too formal and focused presentation of fundamentals of modern computing as rich on interesting/important and indispensible conceptual tools and methods as well as deep/exciting results for undergraduate and graduate students in computing and related areas (engineering, science, mathematics,...). Suitable also as a refernce book or a handbook for all ambitious professionals in computing and related areas with heavy and/or deep use of computing.

Main areas covered by the book: analysis of algorithms, discrete mathematics, automata and formal languages, models of (sequential and parallel) computers, computational complexity, computability and limitations of formal systems, rewriting systems, cryptographyand interactive/cryptographical protocols, interconnection (multiprocessor) networks and communication complexity.

The book has 11 chapters, 214 figures/tables, 277 examples, algorithms/protocols, 574 exercises in the text, 641 exercises/questions at the end of the chapters, 588 bibliographical references, and a detailed index (48 pages).

Emphases are on motivations, illustrations, explanations and presentation of strong concepts, methods and results, including the very recent ones.

The book is organized into three parts. The first part, the first two chapters, presents basic concepts of complexity analysis, probability, number theory and discrete mathematics (from a computing point of view). The second part, chapters 3 to 8, presnets the basics of automata theory, universal computers, complexity theory, computability, rewriting systems (for strings, graphs) and cryptography. The third part, chapters 9 to 11, presents interactive/cryptographic protocols, interconnection (multiprocessor) networks and communication complexity.

The book is suitable for a synthetising course on fundamentals and covers what a graduate should know from the automata-computers-formal languages-complexity part of theory of computing. The book can also be used for a variety of specialized courses on the advanced undergraduate or graduate level. For example, for complexity theory (chapters 4, 5, and potentially also 6, 9 and 11), models of computers (chapters 4 and 10), cryptography and interactive/cryptographic protocols (chapters 8 and 9), automata and formal languages (chapters 3, 7 (and 4)), computability (chapter 6 (and 4), communication networks (chapter 10), communication complexity (chapter 11), analysis of algorithms (chapter 11), discrete mathematics (chapter 2).

The book is to be supported by a web-pages supplement including an additional chapter "Frontiers",.....

Contents

Preface

1. Fundamentals, 76 pages

• Examples
• Solution of Recurrences -- Basic Methods
  • Substitution Method
  • Iteration Method
  • Reduction to Algebraic Equations
• Special Functions
  • Ceiling and Floor Functions
  • Logarithms
  • Binomial Functions - Coefficients
• Solution of Recurrences -- Generating Functions Methods
  • Generating Functions
  • Solution of Recurrences
• Asymptotics
  • An Asymptotic Hierarchy
  • Big Oh, Omega and Theta-notation
  • Relations between Asymptotic Notations
  • Manipulations with O-notations
  • Asymptotic Notation - Summary
• Asymptotics and Recurrences
  • Bootstrapping
  • Analysis of Divide-and-conquer Algorithms
• Primes and Congruences
  • Euclid's Algorithm
  • Primes
  • Congruence arithmetic
• Discrete Square Roots and Logarithms
  • Discrete Square Roots
  • Discrete Logarithm Problem
• Probability and Randomness
  • Discrete probability
  • Bounds on Tails of Binomial Distributions
  • Randomness and Pseudo-random Generators
  • Probabilistic Recurrences
• Asymptotics Complexity Analysis
  • Tasks of Complexity Analysis
  • Methods of Complexity Analysis
  • Efficiency and Feasibility
  • Complexity Classes and Complete problems
  • Pitfalls
• Exercises
• Historical and Bibliographical Comments

• Sets
  • Basic Concepts
  • Representation of Objects by Words nad Sets by Languages
  • Decision and Search Problems
  • Data Structures and Data Types
• Relations
  • Basic Concepts
  • Representation of Relations
  • Transitive and Reflexive Closure
  • Posets
• Functions
  • Basic Concepts
  • Boolean Functions
  • One-way Functions
  • Hash Functions
• Graphs
  • Basic Concepts
  • Graph Representations and Graph Algorithms
  • Matchings and Colorings
  • Graph Traversals
  • Trees
• Languages
  • Basic Concepts
  • Languages, Decision Problems and Boolean Functions
  • Interpretations of Words and Languages
  • Space of Omega-languages
• Algebras
  • Closures
  • Semigroups and Monoids
  • Groups
  • Quasi-rings, Rings and Fields
  • Boolean and Kleene Algebras
• Exercises
• Historical and Bibliographical References

• Finite State Devices
• Finite Automata
  • Basic Concepts
  • Nondeterministic versus Deterministic Finite Automata
  • Minimization of Deterministic Finite Automata
  • Decision Problems
  • String Matching with Finite Automata
• Regular languages
  • Closure Properties
  • Regular Expressions
  • Decision Problems
  • Other Characterizations of Regular Languages
• Finite Transducers
  • Mealy and Moore Machines
  • Finite State Transducers
• Weighted Finite Transducers and Automata
  • Basic concepts
  • Functions computed by WFA
  • Image Generation and Transformation by WFA and WTF
  • Image Compression
• Finite Automata on Infinite Words
  • Buechi and Muller Automata
  • Finite State Control of Reactive Systems
• Limitations of Finite State Machines
• From Finite Automata to Universal Computers
  • Transition Systems
  • Probabilistic Finite Automata
  • Two-way Finite Automata
  • Multi-head Finite Automata
  • Linearly Bounded Automata
• Exercises
• Historical and Bibliographical References

• Turing Machines
  • Basic Concepts
  • Acceptance of Languages and Computation of Functions
  • Programming Techniques, Simulations and Normal Forms
  • Church's Thesis
  • Universal Turing Machines
  • Undecidable and Unsolvable Problems
  • Multi-tape Turing Machines
  • Time Speed-ups and Space Compression
• Random Access Machines
  • Basic model
  • Mutual Simulations of Random Access and Turing Machines
  • Sequential Computation Thesis
  • Straight-line Programs
  • RRAM - Random Access Machines over Reals
• Boolean Circuits Families
  • Boolean Circuits
  • Circuit Complexity of Boolean functions
  • Mutual Simulations of Turing Machines and Families of Circuits
• PRAM -- Parallel RAM
  • Basic model
  • Memory Conflicts
  • PRAM Programming
  • Efficiency of Parallelization
  • PRAM Programming - Continuation
  • Parallel Computation Thesis
  • Relations between CRCR PRAM Models
• Cellular Automata
  • Basic Concepts
  • Case Studies
  • A Normal Form
  • Mutual Simulations of Turing Machines and Cellular Automata
  • Reversible Cellular Automata
• Exercises
• Historical and Bibliographical References

• Nondeterministic Turing Machines
• Complexity Classes, Hierarchies and Tradeoffs
• Reductions and Complete Problems
• NP-complete Problems
  • Direct Proofs of NP-completeness
  • Reduction Methods to prove NP-completeness
  • Analysis of NP-completeness
• Average-case Complexity and Completeness
  • Average Polynomial Time
  • Reductions of Distributional Decision Problems
  • Average-case NP-completeness
• Graph Isomorphism and Prime Recognition
  • Graph Isomorpism and Nonisomorphism
  • Prime Recognition
• NP versus P
  • Role of NP in Computing
  • Structure of NP
  • P = NP Problem
  • Relativization of the P = NP Problem
  • P-completeness
  • Structure of P
  • Functional Version of the P = NP problem
  • Counting problems - Class Sharp P
• Approximability of NP-complete Problems
  • Performance of Approximation Algorithms
  • NP-complete Problems with a Constant Approximation Threshold
  • Travelling Salesman Problem
  • Nonapproximability
  • Complexity Classes
• Randomized Complexity Classes
  • Randomized Algorithms
  • Models and Complexity Classes of Randomized Computing
  • The Complexity Class BPP
• Parallel Complexity Classes
• Beyond NP
  • Between NP and PSPACE --- Polynomial Hierarchy
  • PSPACE-complete Problems
  • Exponential Complexity Classes
  • Far Beyond NP --- with regular expressions only
• Computational Versus Descriptional Complexity
• Exercises
• Historical and Bibliographical References

• Recursive and Recursively Enumerable Sets
• Recursive and Primitive Recursive Functions
  • Primitive Recursive Functions
  • Partial Recursive and Recursive Functions
• Recursive Reals
• Undecidable Problems
  • Rice's Theorem
  • Halting Problem
  • Tiling Problem
  • Thue Problem
  • Post Correspondence Problem
  • Hilbert's Tenth Problem
  • Borderlines between Decidability and Undecidability
  • Degrees of Undecidability
• Limitations of Formal Systems
  • Goedel's Incompleteness Theorem
  • Kolmogorov Complexity: Algorithmic Entropy and Information
  • Chaitin Complexity: Algorithmic Entropy and Information
  • Limitations of Formal Systems to Prove Randomness
  • The Number of Wisdom
  • Kolmogorov-Chaitin Complexity as a Methodology
• Exercises
• Historical and Bibliographical References

• String Rewriting Systems
• Chomsky Grammars and Automata
  • Chomsky Grammars
  • Chomsky Grammars and Turing Machines
  • Context-sensitive Grammars and Linearly Bounded Automata
  • Regular Grammars and Finite Automata
• Context-free Grammars and Languages
  • Basic Concepts
  • Normal Forms
  • Context-free Grammars and Pushdown Automata
  • Recognition and Parsing of Context-free Grammars
  • Context-free Languages
• Lindenmeyer Systems
  • 0L-systems and Growth Functions
  • Graphical Modeling with L-systems
• Graph Rewriting
  • Node Rewriting
  • Edge and Hyperedge Rewriting
• Exercises
• Historical and Bibliographical References

• Cryptosystems and Cryptology
  • Cryptosystems
  • Cryptoanalysis
• Secret-key Cryptosystems
  • Mono-alphabetic Substitution Cryptosystems
  • Poly-alphabetic Substitition Cryptosystems
  • Transposition Cryptosystems
  • Perfect Secrecy Cryptosystems
  • How to Make the Cryptoanalysts' Task Harder
  • DES Cryptosystem
  • Public Distribution of Secret Keys
• Public-key Cryptosystems
  • Trapdoor One-way Functions
  • Knapsack Cryptosystem
  • RSA Cryptosystem
  • Analysis of RSA
• Cryptography and Randomness
  • Cryptographically Strong Pseudo-random Generators
  • Randomized Encryptions
  • Down to Earth and Up
• Digital Signatures
• Exercises
• Historical and Bibliographical References

• Cryptographic Protocols
• Interactive Protocols and Proofs
  • Interactive Proof Systems
  • Interactive Complexity Classes and Shamir's Theorem
  • A Brief History of Proofs
• Zero-knowledge Proofs
  • Examples
  • Theorems with Zero-knowledge Proofs
  • Analysis and Applications of Zero-knowledge Proofs
• Interactive Program Validation
  • Interactive Result Checkers
  • Interactive Self-correcting and Self-testing Programs
• Exercises
• Historical and Bibliographical References

• Basic Networks
  • Networks
  • Basic Network Characteristics
  • Algorithms on Multiprocessor Networks
• Dissemination of Information in Networks
  • Information Dissemination problems
  • Broadcasting and Gossiping in Basic Networks
• Embeddings
  • Basic Concepts and Results
  • Hypercube Embeddings
• Routing
  • Permutation Networks
  • Detrministic Permutation Routing with Preprocessing
  • Deterministic Permutation Routing without Preprocessing
  • Randomized Routing
• Simulations
  • Universal Networks
  • PRAM Simulations
• Layouts
  • Basic Model, Problems and Layouts
  • General Layout Techniques
• Limitations
  • Edge Length of Regular Low Diameter Networks
  • Edge Length of Randomly Connected Networks
• Exercises
• Historical and Bibliographical References

• Examples and Basic Models
  • Basic Model
• Lower Bounds
  • Fooling Set Method
  • Matrix Rank Method
  • Tiling Method
  • Comparison of Methods for Lower Bounds
• Communication Complexity
  • Basic Concepts and Examples
  • Lower Bounds - an Application to VLSI Computing
• Nondeterministic and Randomized Communications
  • Nondeterministic Communications
  • Randomized Communications
• Communication Complexity Classes
• Communicatuion versus Computational Complexity
  • Communication Games
  • Complexity of Communication Games
• Exercises
• Historical and Bibliographical References

Index, 48 pages