Fundamental Problems in Computing

Part I. Selected Reprints from Professor Rosenkrantz’s Seminal Contributions

1. Matrix Equations and Normal Forms forContext-Free Grammars
Daniel J. Rosenkrantz

2. Attributed Translations
P. M. Lewis, D. J. Rosenkrantz, R. E. Stearns

3. An analysis of several heuristics for thetraveling salesman problem
Daniel J. Rosenkrantz, Richard E. Stearns, Philip M. Lewis

4. System Level Concurrency Control forDistributed Database Systems
Daniel J. Rosenkrantz, Richard E. Stearns, Philip M. Lewis

5. Consistency and serializability in concurrent database systems
D. J. Rosenkrantz, R. E. Stearns, P. M. Lewis

6. An efficient method for representing andtransmitting message patterns onmultiprocessor interconnection networks
P. J. Bernhard, D. J. Rosenkrantz

7. Representability ofDesign Objects byAncestor-Controlled Hierarchical Specifications
Lin Yu, Daniel J. Rosenkrantz

8. The Complexity ofProcessing Hierarchical Specifications
Daniel J. Rosenkrantz, Harry B. Hunt

9. Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems
R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Harry B. Hunt

10. Efficient Algorithms for Segmentation of Item-Set Time Series
Parvathi Chundi, Daniel J. Rosenkrantz

Part II. Contributed Articles

11. Sums-of-Products and Subproblem Independence
Richard E. Stearns, Harry B. Hunt

12. An Optimistic Concurrency Control Protocol for Replicated Databases
Yuri Breitbart, Henry F. Korth, Avi Silberschatz

13. SNAPSHOT Isolation: Why Do Some People Call it SERIALIZABLE?
Philip Lewis

14. A Richer Understanding of the Complexity of Election Systems
Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe

15. Fully Dynamic Bin Packing
Zoran Ivkovi?, Errol L. Lloyd

16. Online Job Admission
Sven O. Krumke, Rob Stee, Stephan Westphal

17. A Survey of Graph Algorithms Under Extended Streaming Models of Computation
Thomas C. O’Connell

18. Interactions among human behavior, social networks, and societal infrastructures: A Case Study in Computational Epidemiology
Christopher L. Barrett, Keith Bisset, Jiangzhuo Chen, Stephen Eubank, Bryan Lewis, V. S. Anil Kumar, Madhav V. Marathe, Henning S. Mortveit

Keywords: Computer Science, Programming Languages, Compilers, Interpreters, Mathematical Logic and Formal Languages, Logic Design