Information Processing Letters, Volume 16

Volume 16, Number 1, 24 January 1983

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

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

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

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

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