Handbook of Theoretical Computer Science: 2 Volume Set

Handbook of Theoretical Computer Science: 2 Volume Set

Paperback

$141.38 $170.00 Save 17% Current price is $141.38, Original price is $170. You Save 17%.
View All Available Formats & Editions

Overview

The Handbook of Theoretical Computer Science provides professionals and students with a comprehensive overview of the main results and developments in this rapidly evolving field. Volume A covers models of computation, complexity theory, data structures, and efficient computation in many recognized subdisciplines of theoretical computer science. Volume B takes up the theory of automata and rewriting systems, the foundations of modern programming languages, and logics for program specification and verification, and presents several studies on the theoretic modeling of advanced information processing.

The two volumes contain thirty-seven chapters, with extensive chapter references and individual tables of contents for each chapter. There are 5,387 entry subject indexes that include notational symbols, and a list of contributors and affiliations in each volume.

Product Details

ISBN-13: 9780262720205
Publisher: MIT Press
Publication date: 01/04/1994
Pages: 2
Product dimensions: 8.00(w) x 10.00(h) x 3.90(d)

About the Author

Matthew Paterson is Senior Lecturer in International Relations at Keele University. He is author of Global Warming and Global Politics (1996) and Understanding Global Environmental Politics (2003), as well as many articles and book chapters on these subjects. He is currently working on cars and global environmental politics. He is Associate Editor of Global Environmental Politics.

Table of Contents

PREFACE ..... i

LIST OF CONTRIBUTORS TO VOLUME A ..... iii

CONTENTS ..... v

Chapter 1 MACHINE MODELS AND SIMULATIONS ..... 1
P.van Emde Boas

1. Introduction ..... 3
2. Sequential machine models ..... 16
3. The second machine class ..... 38
4. Parallel machine models outside the second machine class ..... 54
Acknowledgment ..... 60
References ..... 61
Chapter 2 A CATALOG OF COMPLEXITY CLASSES ..... 67
D.S. Johnson
1. Preliminaries ..... 69
2. Presumably intractable problems ..... 83
3. Provably intractable problems ..... 101
4. Classes that count ..... 106
5. Inside p ..... 125
6. New developments: tables and figures ..... 143
References ..... 152
Chapter 3 MACHINE-INDEPENDENT COMPLEXITY THEORY ..... 163
J.I. Seiferas
1. Introductions ..... 165
2. Simple Turing machines and space complexity ..... 165
3. Recursion, padding and compression ..... 167
4. Gaps and arbitrary speed-up ..... 171
5. Effective speed-up ..... 175
6. Fundamental Theorem for STM space ..... 177
7. Machine independence ..... 178
Acknowledgment ..... 185
References ..... 185
Chapter 4 KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS ..... 187
M. Li and P.M.B. Vitanyi
1. Introduction ..... 189
2. Mathematical theory ..... 196
3. Applications of compressibility ..... 214
4. Example of an application in mathematics: weak prime number theorems ..... 221
5. Application of incompressibility: proving lower bounds ..... 222
6. Resource-bounded Kolmogorov complexity and its applications ..... 236
7. Conclusion .....247
Acknowledgment ..... 247
References ..... 248
Chapter 5 ALGORITHMS FOR FINDING PATTERNS IN STRINGS ..... 255
A.V. Aho
1. Introduction ..... 257
2. Notations for patterns ..... 258
3. Matching keywords ..... 262
4. Matching sets of keywords ..... 273
5. Matching regular expressions ..... 282
6. Related problems ..... 288
7. Concluding remarks ..... 295
Acknowledgments ..... 295
References ..... 295
Chapter 6 DATA STRUCTURES ..... 301
K. Mehlhorn and A. Tsakalidis
1. Introduction ..... 303
2. The dictionary problem ..... 305
3. The weighted dictionary problem and self-organizing data structures ..... 319
4. Persistence ..... 323
5. The Union-Split-Find problem ..... 324
6. Priority queues ..... 326
7. Nearest common ancestors ..... 328
8. Selection ..... 329
9. Merging ..... 331
10. Dynamization techniques ..... 332
References ..... 334
CHAPTER 7 COMPUTATIONAL GEOMETRY ..... 343
F.F. Yao
1. Introduction ..... 345
2. Techniques and paradigms ..... 345
3. Convex hulls ..... 348
4. Voronoi diagram ..... 352
5. Proximity problems ..... 356
6. Linear programming ..... 360
7. Triangulation and decomposition ..... 364
8. Planer point location ..... 366
9. Multidimensional trees ..... 368
10. Range search ..... 370
11. Visibility computations ..... 374
12. Combinatorial geometry ..... 376
13. Other topics ..... 378
14. Conclusion ..... 380
References ..... 380
CHAPTER 8 ALGORITHMIC MOTION PLANNING IN ROBOTICS ..... 391
J.T. Schwartz and M. Sharir
1. Introduction ..... 393
2. Statement of the problem ..... 394
3. Motion planning in static and known environments ..... 397
4. Variants of the motion planning problem ..... 415
5. Results in computational geometry relevant to motion planning ..... 421
Acknowledgment ..... 425
Reference ..... 425
CHAPTER 9 AVERAGE-CASE ANALYSIS OF ALGORITHMS AND DATA STRUCTURES ..... 431
J.S. Vitter and Ph. Flajolet
0. Introduction ..... 433
1. Combinatorial enumerations ..... 436
2. Asymptotic methods ..... 445
3. Sorting algorithms ..... 458
4. Recursive decompositions and algorithms on trees ..... 473
5.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews