Information Processing Letters, Volume 19

Volume 19, Number 1, 26 July 1984

Hari Madduri, Raphael A. Finkel: Extension of the Banker's Algorithm for Resource Allocation in a Distributed Operating System. 1-8
Michio Oyamaguchi: Some Remarks on Subclass Containment Problems for Several Classes of DPDA's. 9-12
Nam Sung Woo, Carl H. Smith, Ashok K. Agrawala: A Proof of the Determinacy Property of the Data Flow Schema. 13-16
J. R. Parker: On Converting Character Strings to Integers. 17-19
Ulrich Bechtold, Klaus Küspert: On the Use of Extendible Hashing Without Hashing. 21-26
Ulrich Faigle, Rainer Schrader: Minimizing Completion Time for a Class of Scheduling Problems. 27-29
Walter J. Savitch, Paul M. B. Vitányi: On the Power of Real-Time Two-Way Multihead Finite Automata With Jumps. 31-35
Alan A. Bertossi: Dominating Sets for Split and Bipartite Graphs. 37-40
P. A. Subrahmanyam, Jia-Huai You: On Embedding Functions in Logic. 41-46
Selim G. Akl: An Optimal Algorithm for Parallel Selection. 47-50
Udi Manber: A Probabilistic Lower Bound for Checking Disjointness of Sets. 51-53
Paul G. Spirakis, Chee-Keng Yap: Strong NP-Hardness of Moving Many Discs. 55-59

Helmut Alt, Kurt Mehlhorn, J. Ian Munro: Partial Match Retrieval in Implicit Data Structures. 61-65
Alain J. Martin, Martin Rem: A Presentation of the Fibonacci Algorithm. 67-68
Geoff P. McKeown, Victor J. Rayward-Smith: Communication Problems on MIMD Parallel Computers. 69-73
Prashant Palvia, Salvatore T. March: Approximating Block Accesses in Database Organizations. 75-79
Emilio Luque, Ana Ripoll: Integer Linear Programming for Microprograms Register Allocation. 81-85
Ewa Klupsz: A Linear Algorithm of a Deadlock Avoidance for Nonpreemptible Resources. 87-94
Grazia Lotti: Area-Time Tradeoff for Rectangular Matrix Multiplication in VLSI Models. 95-98
Witold Lipski Jr.: An O(n log n) Manhattan Path Algorithm. 99-102
Elaine J. Weyuker: The Complexity of Data Flow Criteria for Test Data Selection. 103-109

Adi Shamir, Claus-Peter Schnorr: Cryptanalysis of Certain Variants of Rabin's Signature Scheme. 113-115
Joseph M. Treat, Timothy A. Budd: Extensions to Grid Selector Composition and Compilation in APL. 117-123
David Avis: Non-Partitionable Point Sets. 125-129
Peter Eades, Brendan D. McKay: An Algorithm for Generating Subsets of Fixed Size With a Strong Minimal Change Property. 131-133
R. Dale Johnson, Barrett R. Bryant: Formal Syntax Methods for Natural Language. 135-143
Tomasz Kowaltowski, Antonio Palma: Another Solution of the Mutual Exclusion Problem. 145-146
R. G. Gupta, V. S. P. Srivastava: On Synthesis of Scheduling Algorithms. 147-150
Joachim Biskup: Some Variants of the Take-Grant Protection Model. 151-156
Dario Maio, Maria Rita Scalas, Paolo Tiberio: On Estimating Access Costs in Relational Databases. 157-161

Wojciech Rytter: On Linear Context-Free Languages and One-Way Multihead Automata. 163-166
Marek Chrobak, Bogdan S. Chlebus: Probabilistic Turing Machines and Recursively Enumerable Dedekind Cuts. 167-171
Philippe Darondeau, Laurent Kott: Towards a Formal Proof System for omega-Rational Expressions. 173-177
Marek Chrobak: A Note on Bounded-Reversal Multipushdown Machines. 179-180
Dick Grune: How to Produce All Sentences From a Two-Level Grammar. 181-185
Arturo Carpi: On the Centers of the Set of Weakly Square-Free Words on a Two Letter Alphabet. 187-190
Jaroslav Král: On Software Equations. 191-196
Michael Kallay: The Complexity of Incremental Convex Hull Algorithms in R^d. 197
Clement H. C. Leung: Approximate Storage Utilisation of B-Trees: A Simple Derivation and Generalisations. 199-201
T. R. Walsh: How Evenly Should One Divide to Conquer Quickly? 203-208
Lawrence W. Dowdy, Derek L. Eager, Karen D. Gordon, Lawrence V. Saxton: Throughput Concavity and Response Time Convexity. 209-212

Juhani Karhumäki, Derick Wood: Inverse Morphic Equivalence on Languages. 213-218
Greg N. Frederickson: On Linear-Time Algorithms for Five-Coloring Planar Graphs. 219-224
Erkki Mäkinen: On Derivation Preservation. 225-228
Derick Wood: The Contour Problem for Rectilinear Polygons. 229-236
Paul Bourret: How to Estimate the Sizes of Domains. 237-243
George Tourlakis: An Inductive Number-Theoretic Characterization of NP. 245-247
Jozef Vyskoc: A Note on Boolean Matrix Multiplication. 249-251
Pierre McKenzie: Permutations of Bounded Degree Generate Groups of Polynomial Diameter. 253-254
Goker Gursel, Peter Scheuermann: Asserting the Optimality of Serial SJRPs in Processing Simple Queries in Chain Networks. 255-260