| Foreword | 6 |
|---|
| Preface and Introduction | 7 |
|---|
| References | 16 |
|---|
| Selected Reprints from Professor Rosenkrantz's Seminal Contributions | 21 |
|---|
| Matrix Equations and Normal Forms for Context-Free Grammars | 22 |
| Preliminaries | 22 |
| Systems of Equations | 23 |
| Regular Expressions and the Closure of a Matrix | 24 |
| Normal Form with Terminal Production Heads | 25 |
| Normal Form with Terminal Heads and Tails | 28 |
| References | 29 |
| Attributed Translations | 30 |
| Introduction | 30 |
| Translation Grammars | 32 |
| Attributed Translations | 33 |
| Attributed Translation Grammars | 33 |
| Examples | 36 |
| Attributed Pushdown Machines | 43 |
| Performing Translations Nondeterministically | 45 |
| Performing Translations Deterministically | 51 |
| Performing Arbitrary Translations | 57 |
| Summary | 58 |
| References | 59 |
| An analysis of several heuristics for the traveling salesman problem | 60 |
| Introduction | 61 |
| Nearest Neighbor Algorithm | 62 |
| Insertion Methods | 69 |
| Nearest Insertion and Cheapest Insertion | 72 |
| Farthest Insert | 77 |
| Some Other Approximation Methods | 78 |
| k-Optimality | 80 |
| References | 83 |
| System Level Concurrency Control for Distributed Database Systems | 84 |
| Introduction | 85 |
| Consistency | 87 |
| Process Termination and Abortion | 88 |
| Linearizing Concurrency Controls | 89 |
| Conflicts | 90 |
| Strict Concurrency Controls | 91 |
| Responses to Conflicts | 94 |
| Waiting Forever | 95 |
| Fixed Order Concurrency Controls | 98 |
| Restarting Forever | 100 |
| The WAIT-DIE System | 101 |
| The Wound-Wait System | 101 |
| Comparison of WAIT-DIE and WOUND-WAIT Systems | 103 |
| Centralized Concurrency Control | 104 |
| Hybrid Concurrency Controls | 105 |
| References | 109 |
| Consistency and serializability in concurrent database systems | 111 |
| Introduction | 112 |
| Concurrency Control | 115 |
| Databases | 116 |
| Transactions | 116 |
| Version Graphs | 118 |
| Version Graph Analysis | 120 |
| Datatraces | 123 |
| Main Results | 126 |
| Assuring Consistency | 127 |
| The Converse Result | 129 |
| The Read-Before-Write Assumption | 136 |
| Time Assumptions | 138 |
| Conclusion | 142 |
| References | 143 |
| An efficient method for representing and transmitting message patterns on multiprocessor interconnection networks | 145 |
| Introduction | 146 |
| The Omega Network | 149 |
| Definition of a Mask Formalism | 151 |
| Mask Normal Form | 153 |
| Classes of Message Patterns Representable by (s,d)-Masks | 154 |
| (s,d)-Masks and Detecting Congestion | 156 |
| Detecting Conflicts in an (s,d)-Mask | 158 |
| Detecting Congestion in an (s,d)-Mask | 162 |
| Minimum Round Partitioning for (s,d)-Masks | 164 |
| Minimum Round Partitioning for Non-Broadcast Omega Networks | 165 |
| Minimum Round Partitioning for Broadcast Omega Networks | 169 |
| Conclusion | 171 |
| References | 172 |
| Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications | 174 |
| Introduction | 175 |
| Basic Definitions and Concepts | 182 |
| Expressive Power of the VDAG Model | 187 |
| VDAG Construction | 191 |
| Stamp Uniqueness Property and the Effect of Bounded Stamp Multiplicity | 198 |
| Construction of
|
