Fundamental Problems in Computing is in honor of Professor Daniel J. Rosenkrantz, a distinguished researcher in Computer Science. Professor Rosenkrantz has made seminal contributions to many subareas of Computer Science including formal languages and compilers, automata theory, algorithms, database systems, very large scale integrated systems, fault-tolerant computing and discrete dynamical systems. For many years, Professor Rosenkrantz served as the Editor-in-Chief of the Journal of the Association for Computing Machinery (JACM), a very prestigious archival journal in Computer Science. His contributions to Computer Science have earned him many awards including the Fellowship from ACM and the ACM SIGMOD Contributions Award.
Author(s): Sekharipuram S. Ravi, Sandeep K. Shukla
Edition: 1
Publisher: Springer
Year: 2009
Language: English
Pages: 542
Preliminaries......Page 25
Systems of Equations......Page 26
Regular Expressions and the Closure of a Matrix......Page 27
Normal Form with Terminal Production Heads......Page 28
Normal Form with Terminal Heads and Tails......Page 31
Introduction......Page 35
Translation Grammars......Page 37
Attributed Translation Grammars......Page 38
Examples......Page 41
Attributed Pushdown Machines......Page 48
Performing Translations Nondeterministically......Page 50
Performing Translations Deterministically......Page 56
Performing Arbitrary Translations......Page 62
Summary......Page 63
An analysis of several heuristics for the traveling salesman problem......Page 67
Introduction......Page 68
Nearest Neighbor Algorithm......Page 69
Insertion Methods......Page 76
Nearest Insertion and Cheapest Insertion......Page 79
Farthest Insert......Page 84
Some Other Approximation Methods......Page 85
k-Optimality......Page 87
System Level Concurrency Control for Distributed Database Systems......Page 93
Introduction......Page 94
Consistency......Page 96
Process Termination and Abortion......Page 97
Linearizing Concurrency Controls......Page 98
Conflicts......Page 99
Strict Concurrency Controls......Page 100
Responses to Conflicts......Page 103
Waiting Forever......Page 104
Fixed Order Concurrency Controls......Page 107
Restarting Forever......Page 109
The Wound-Wait System......Page 110
Comparison of WAIT-DIE and WOUND-WAIT Systems......Page 112
Centralized Concurrency Control......Page 113
Hybrid Concurrency Controls......Page 114
Consistency and serializability in concurrent database systems......Page 121
Introduction......Page 122
Concurrency Control......Page 125
Transactions......Page 126
Version Graphs......Page 128
Version Graph Analysis......Page 130
Datatraces......Page 133
Main Results......Page 136
Assuring Consistency......Page 137
The Converse Result......Page 139
The Read-Before-Write Assumption......Page 146
Time Assumptions......Page 148
Conclusion......Page 152
An efficient method for representing and transmitting message patterns on multiprocessor interconnection networks......Page 155
Introduction......Page 156
The Omega Network......Page 159
Definition of a Mask Formalism......Page 161
Mask Normal Form......Page 163
Classes of Message Patterns Representable by (s,d)-Masks......Page 164
(s,d)-Masks and Detecting Congestion......Page 166
Detecting Conflicts in an (s,d)-Mask......Page 168
Detecting Congestion in an (s,d)-Mask......Page 172
Minimum Round Partitioning for (s,d)-Masks......Page 174
Minimum Round Partitioning for Non-Broadcast Omega Networks......Page 175
Minimum Round Partitioning for Broadcast Omega Networks......Page 179
Conclusion......Page 181
Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications......Page 185
Introduction......Page 186
Basic Definitions and Concepts......Page 193
Expressive Power of the VDAG Model......Page 198
VDAG Construction......Page 202
Stamp Uniqueness Property and the Effect of Bounded Stamp Multiplicity......Page 209
Construction of Number Functions......Page 215
Handling Non-VDAG-Generable Forests......Page 218
Relative Conciseness of VDAG Model......Page 219
Automatic Simplification......Page 222
Conclusion......Page 227
The Complexity of Processing Hierarchical Specifications......Page 231
Introduction......Page 232
Definitions and Terminology of Hierarchical Specifications......Page 234
Linear Space Simulation of Weakly Acyclic Circuits......Page 238
Acyclic Circuits: Lower Bounds......Page 243
2O(n) time Simulation of Acyclic Circuits......Page 248
Analysis Problems for Circuits with Cycles......Page 254
Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems......Page 263
Introduction and Motivation......Page 264
Basic Definitions and Problem Formulations......Page 265
Approximation Algorithms......Page 267
Related Work......Page 268
Degree-Constrained Node-Weighted Steiner Trees......Page 269
A Procedure to Find Minimum Ratio Spiders......Page 270
Bounding the Total Degree of Deleted Nodes......Page 274
Spider Decompositions and an Averaging Lemma......Page 275
A Potential Function Argument......Page 277
Algorithms Under Triangle Inequality......Page 279
Results for Spanning Trees......Page 280
Extension to Higher Connectivities......Page 281
Hardness Results for Spanning Tree Problems......Page 283
Hardness Results for Steiner Tree Problems......Page 284
Concluding Remarks......Page 285
Subsequent Work......Page 286
Efficient Algorithms for Segmentation of Item-Set Time Series......Page 291
Introduction......Page 292
Terminology and Definitions......Page 296
Segment Difference Computation for the Count Measure......Page 297
Segment Difference Computation for the Density Measure......Page 302
Optimal Segmentations......Page 305
Comparison of Optimal and Oblivious Segmentations......Page 307
Study of the Performance of Proposed Methods......Page 313
Related Work......Page 315
Conclusions......Page 316
Introduction......Page 325
Examples......Page 327
The Plus and Times Operators......Page 334
Quantified Sums......Page 337
Connection to Memory-Bounded Nondeterminism......Page 342
Measures of Independence......Page 347
Thank You Dan......Page 348
An Optimistic Concurrency Control Protocol for Replicated Databases......Page 351
Introduction......Page 352
Related Work......Page 353
System Model......Page 355
Virtual Sites......Page 359
Replication Graph......Page 360
Commit-Oriented Protocol (COP)......Page 363
Message Overhead......Page 367
Failures and Recovery......Page 369
Conclusions......Page 371
Introduction......Page 377
Correctness of Transaction Processing Systems......Page 378
Concurrency Controls, Two-Phase Locking, and Isolation Levels......Page 379
SNAPSHOT Isolation......Page 380
Non-Serializable but Correct Execution......Page 382
Phantoms at SNAPSHOT Isolation......Page 383
A Sufficient Condition for Serializable Execution at SNAPSHOT Isolation......Page 384
The Infrastructure/State Design Pattern......Page 386
Automatic Constraint Checking......Page 387
Read-Only, Update-Only, and Read-Update Transactions......Page 388
State and Infrastructure Items and Transactions......Page 389
The Infrastructure/State Design Pattern......Page 390
State and Infrastructure Items and Transactions......Page 392
The Disjoint-Predicate-Write Property......Page 393
Conclusion......Page 394
Dedication......Page 395
A Richer Understanding of the Complexity of Election Systems......Page 399
Introduction......Page 400
Elections and Election Systems: Preliminaries......Page 401
Complexity of Winning: Dodgson's 1876 Election System......Page 404
Complexity of Manipulation and Bribery: Scoring Systems and Dichotomy Theorems......Page 411
Complexity of Control: Making Someone Win or Keeping Someone From Winning......Page 419
Conclusions......Page 426
Fully Dynamic Bin Packing......Page 431
Background-Off-Line and On-Line Bin Packing......Page 432
The Performance of Fully Dynamic Approximation Algorithms......Page 434
Moving a Constant Number of Items Per Operation......Page 435
A 5/4-Competitive Algorithm for Fully Dynamic Bin Packing......Page 439
Some Definitions......Page 440
LLS-Maximality and M-Thoroughness......Page 442
MMP Insert and Delete operations-The Key Concepts......Page 444
The Running Time of MMP Is Theta(logn)......Page 448
Uniform Algorithms for Partially Dynamic Bin Packing......Page 449
Amortized Algorithms for Partially Dynamic Bin Packing......Page 450
Conclusion......Page 454
Partially Dynamic Bin Packing......Page 455
Online Job Admission......Page 459
Introduction......Page 460
Our Results......Page 462
Previous Work......Page 463
The Offline Problem......Page 464
Lower Bounds......Page 465
A Greedy-Type Deterministic Algorithm......Page 471
An Algorithm Based on Classify and Randomly Select......Page 472
An Improved Deterministic Algorithm......Page 473
Conclusions......Page 476
Introduction......Page 479
Communication Complexity......Page 481
Semi-Streaming Model......Page 484
Spanners......Page 485
Sparsification......Page 486
W-Stream......Page 487
Connected Components in W-Stream......Page 488
Single-Source Shortest Paths......Page 489
The Stream-Sort Model......Page 492
Connected Components in Stream-Sort......Page 493
Thank You Dan......Page 497
Interactions among human behavior, social networks, and societal infrastructures: A Case Study in Computational Epidemiology......Page 501
Introduction......Page 502
The PIN Problem in Computational Epidemiology......Page 503
Network Based Computational Epidemiology......Page 505
SimDemics......Page 506
A Mathematical Model to Capture Co-Evolution......Page 508
Specifying PIN Problems in CE Using Co-Evolving Discrete Dynamical Systems......Page 510
Basic Experimental Setup......Page 512
Experiment 1......Page 513
Experiment 2......Page 517
Comparing Adaptive and Non-Adaptive Strategies......Page 520
Preliminaries: A Simplified Model......Page 521
Policy Planning Problems......Page 522
Individual Behavior Problems: A Game Theoretic/ Dynamical Systems Viewpoint......Page 524
Discussion of the Different Formulations......Page 526
Thank You Dan......Page 528
-Subject Index......Page 0
