Information Processing Letters, Volume 16

Volume 16, Number 1, 24 January 1983

Friedhelm Meyer auf der Heide: Infinite Cube-Connected Cycles. 1-2
Alan A. Bertossi, Maurizio A. Bonuccelli: Preemptive Scheduling of Periodic Jobs in Uniform Multiprocessor Systems. 3-6
Andrzej Ehrenfeucht, Grzegorz Rozenberg: On the Subword Complexity of Locally Catenative D0L Languages. 7-9
Vitit Kantabutra: Traveling Salesman Cycles are not Always Subgraphs of Voronoi Duals. 11-12
Ronald Fagin, Moshe Y. Vardi: Armstrong Databases for Functional and Inclusion Dependencies. 13-19
Aarni Perko: A Representation of Disjoint Sets with Fast Initialization. 21
Kenneth L. Clarkson: A Modification of the Greedy Algorithm for Vertex Cover. 23-25
Michel Latteux: On a Language Without Star. 27-30
Yves Métivier: About the Rewriting Systems Produced by the Knuth-Bendix Completion Algorithm. 31-34
Ralf Hartmut Güting: Stabbing C-Oriented Polygons. 35-40
Ingo Wegener: Relating Monotone Formula Size and Monotone Depth of Boolean Functions. 41-42
Lewis Neale Lester: Accuracy of Approximating Queueing Network Departure Processes With Independent Renewal Processes. 43-48

Joanna Jedrzejowicz: On the Enlargement of the Class of Regular Languages by the Shuffle Closure. 51-54
Juris Hartmanis: On Sparse Sets in NP - P. 55-60
Lloyd Allison: Stable Marriages by Coroutines. 61-65
Christopher W. Fraser: A Generalization of Two Code Ordering Optimizations. 67-70
Stefan Eicholz: Optimal Networks for Distributing Nonsequential Programs. 71-74
Bernard Chazelle: A Decision Procedure for Optimal Polyhedron Partitioning. 75-78
Bowen Alpern, Fred B. Schneider: Key Exchange Using `Keyless Cryptography'. 79-81
Micha Hofri: Should the Two-Headed Disk be Greedy? - Yes, it Should. 83-85
Dan Gusfield: Connectivity and Edge-Disjoint Spanning Trees. 87-89
T. R. Walsh: Iteration Strikes Back - at the Cyclic Towers of Hanoi. 91-93
Toshihide Ibaraki, Naoki Katoh: On-Line Computation of Transitive Closures of Graphs. 95-97
Christopher Wood, Eduardo B. Fernández, Tomás Lang: Minimization of Demand Paging for the LRU Stack Model of Program Behavior. 99-104

Robert L. Constable: Programs as Proofs: A Synopsis. 105-112
Robert J. McGlinn: Is SSS* Better Than Alpha-Beta? 113-120
Eljas Soisalon-Soininen: On Computing Approximate Convex Hulls. 121-126
Wojciech Rytter: Time Complexity of Loop-Free Two-Way Pushdown Automata. 127-129
Markku Tamminen: Analysis of N-Trees. 131-137
Toshitsugu Yuba, Yoshinori Yamaguchi, Toshio Shimada: A Control Mechanism of a Lisp-Based Data-Driven Machine. 139-143
Rakesh Agrawal, David J. DeWitt: Updating Hypothetical Data Bases. 145-146
I. K. Rystsov: Polynomial Complete Problems in Automata Theory. 147-151
Marco A. Casanova: The Theory of Functional and Subset Dependencies Over Relational Expressions. 153-160

Jean-Luc Deleage: An Application of a Transfer Lemma. 161-163
Stefan Hertel: Smoothsort's Behavior on Presorted Sequences. 165-170
Greg N. Frederickson: Scheduling Unit-Time Tasks With Integer Release Times and Deadlines. 171-173
Errol L. Lloyd: On a Simple Deadlock Recovery Problem. 175-178
Maxime Crochemore, Michael Le Rest, Philippe Wender: An Optimal Test on Finite Unavoidable Sets of Words. 179-180
Chee-Keng Yap: A Hybrid Algorithm for the Shortest Path Between Two Nodes in the Presence of Few Negative Arcs. 181-182
Takao Tsuda, Takashi Sato, Takaaki Tatsumi: Generalization of Floyd's Model on Permuting Information in Idealized Two-Level Storage. 183-188
Masanori Fushimi: Increasing the Orders of Equidistribution of the Leading Bits of the Tausworthe Sequence. 189-192
Bernard Chazelle: An Improved Algorithm for the Fixed-Radius Neighbor Problem. 193-198
Wojciech Rytter: A Simulation Result for Two-Way Pushdown Automata. 199-202
Annalisa Bossi, Nicoletta Cocco, Livio Colussi: A Divide-and-Conquer Approach to General Context-Free Parsing. 203-208
Uwe Schöning: On the Dtructure of Delta^p₂. 209-211

Edsger W. Dijkstra, W. H. J. Feijen, A. J. M. van Gasteren: Derivation of a Termination Detection Algorithm for Distributed Computations. 217-219
Andrzej Duda: The Effects of Checkpointing on Program Execution Time. 221-229
Arturo Carpi: On the Size of a Square-Free Morphism on a Three Letter Alphabet. 231-235
Fionn Murtagh: Expected-Time Complexity Results for Hierarchic Clustering Algorithms Which Use Cluster Centres. 237-241
Kazumasa Ozawa: Considerations on the Similarity Measures Between Index Terms. 243-246
Jacques Cohen: A Note on a Fast Algorithm for Sparse Matrix Multiplication. 247-248
John Zahorjan, Barbara J. Bell, Kenneth C. Sevcik: Estimating Block Transfers When Record Access Probabilities are Non-Uniform. 249-252
Robert Endre Tarjan: Updating a Balanced Search Tree in O(1) Rotations. 253-257
Hans-Peter Kriegel, Y. S. Kwong: Insertion-Safeness in Balanced Trees. 259-264
Rudolf Freund: Init and Anf Operating on omega-Languages. 265-269