Information Processing Letters, Volume 57

Volume 57, Number 1, 15 January 1996

• Subrata Kumar Das:
  Modal Logics in the Theory of Relational Databases. 1-7
  
• Dennis M. Volpano:
  Lower Bounds on Type Checking Overloading. 9-13
  
• Robert Harper:
  A Note on ``A Simplified Account of Polymorphic References''. 15-16
  
• Akio Yanbe, Kouichi Sakurai:
  A Short Certificate of the Number of Universal Optimal Strategies for Stopping Simple Stochastic Games. 17-24
  
• Michael W. Herman, Waldemar W. Koczkodaj:
  A Monte Carlo Study of Parwise Comparison. 25-29
  
• Vlado Dancík:
  Complexity of Boolean Functions Over Bases with Unbounded Fan-In Gates. 31-34
  
• Maciej Drozdowski:
  Real-Time Scheduling of Linear Speedup Parallel Tasks. 35-40
  
• Dyi-Rong Duh, Gen-Huey Chen, D. Frank Hsu:
  Combinatorial Properties of Generalized Hypercube Graphs. 41-45
  
• Quingbo Xue:
  On a Class of Square-Free Graphs. 47-48
  
• Wei-Bin Lee, Chin-Chen Chang:
  Integrating Authentication in Public Key Distribution System. 49-52
  
• Donatella Merlini, Renzo Sprugnoli, M. Cecilia Verri:
  A Uniform Model for the Storage Utilization of B-Tree-Like Structures. 53-58
  

Volume 57, Number 2, 29 January 1996

• Marius Zimand:
  A High-Low Kolmogorov Complexity Law Equivalent to the 0-1 Law. 59-64
  
• Norbert Blum:
  An O(n log n) Implementation of the Standard Method for Minimizing n-State Finite Automata. 65-59
  
• Anca Muscholl, Holger Petersen:
  A Note on the Commutative Closure of Star-Free Languages. 71-74
  
• Shahram Ghandeharizadeh, Doug Ierardi, Roger Zimmermann:
  An On-Line Algorithm to Optimize File Layout in a Dynamic Environment. 75-81
  
• Oscar Garrido, Stefan Jarominek, Andrzej Lingas, Wojciech Rytter:
  A Simple Randomized Parallel Algorithm for Maximal f-Matchings. 83-87
  
• Bengt Aspvall, Christos Levcopoulos, Andrzej Lingas, Robert Storlind:
  On 2-QBF Truth Testing in Parallel. 89-93
  
• Guozhu Dong, Jianwen Su:
  Conjunctive Query Containment with Respect to Views and Constraints. 95-102
  
• Xiaotie Deng:
  A Lower Bound for Communication in the Crossbar. 103-108
  
• Rolf Fagerberg:
  A Generalization of Binomial Queues. 109-114
  
• Amiya Nayak, Vincenzo Acciaro, Paolo Gissi:
  A Note on Isomorphic Chordal Rings (Erratum). 115
  

Volume 57, Number 3, 12 February 1996

• Peter Clote:
  A Note on the Monotone Complexity of 2-REF. 117-123
  
• G. Dányi, Zoltán Fülöp:
  A Note on the Equivalence Problem of E-Patterns. 125-128
  
• Christos Levcopoulos, Drago Krznaric:
  Tight Lower Bounds for Minimum Weight-Triangulation Heuristics. 129-135
  
• Judy Goldsmith, Steven Homer:
  Scalability and the Isomorphism Problem. 137-143
  
• Tsong Yueh Chen, Yuen-Tak Yu:
  A More General Sufficient Condition for Partition Testing to be Better than Random Testing. 145-149
  
• Paola Alimonti:
  New Local Search Approximation Techniques for Maximum Generalized Satisfiability Problems. 151-158
  
• Michael Müller, Christine Rüb, Wolfgang Rülling:
  A Circuit for Exact Summation of Floating-Points Numbers. 159-163
  
• Manuel Abellanas, Jesus Garcia-Lopez, Gregorio Hernández-Peñalver, Ferran Hurtado, Oriol Serra, Jorge Urrutia:
  Onion Polygonizations. 165-173
  

Volume 57, Number 4, 26 February 1996

• Yves Métivier, Nasser Saheb:
  Medians and Centres of Polyominoes. 175-181
  
• Premkumar Vadapalli, Pradip K. Srimani:
  Shortest Routing in Trivalent Cayley Graph Network. 183-188
  
• Javed A. Aslam, Scott E. Decatur:
  On the Sample Complexity of Noise-Tolerant Learning. 189-195
  
• Kevin Cattell, Michael J. Dinneen, Michael R. Fellows:
  A Simple Linear-Time Algorithm for Finding Path-Decompositions of Small Width. 197-203
  
• M. Manzur Murshed, M. Kaykobad:
  Seek Distances in Two-Headed Disk Systems. 205-209
  
• Kenneth Baclawski, Dan A. Simovici:
  A Characterization of the Information Content of a Classification. 211-214
  
• Antonios Symvonis:
  Routing on Trees. 215-223
  
• Margus Veanes, Jonas Barklund:
  On the Number of Edges in Cycletrees. 225-229
  

Volume 57, Number 5, 11 March 1996

• Luca Trevisan:
  A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees. 231-236
  
• Ran Canetti:
  More on BPP and the Polynomial-Time Hierarchy. 237-241
  
• Hagit Attiya, Roy Friedman:
  Limitations of Fast Consistency Conditions for Distributed Shared Memories. 243-248
  
• Elias Koutsoupias, Christos H. Papadimitriou:
  The 2-Evader Problem. 249-252
  
• William Lenhart, Giuseppe Liotta:
  Drawing Outerplanar Minimum Weight Triangulations. 253-260
  
• Thomas W. Cusick:
  Bounds on the Number of Functions Satisfying the Strict Avalanche Criterion. 261-263
  
• Suresh Viswanathan, Éva Czabarka, Abhijit Sengupta:
  On Fault-Tolerant Embedding of Hamiltonian Circuits in Line Digraph Interconnection Networks. 265-271
  
• Sridhar Seshadri, Doron Rotem:
  The Two Headed Disk: Stochastic Dominance of the Greedy Policy. 273-277
  
• Angelo Monti, Alessandro Roncato:
  A Gap Theorem for the Anonymous Torus. 279-285
  
• Chongkye Rhee, Y. Daniel Liang:
  An NC Algorithm for the Clique Cover Problem in Cocomparability Graphs and its Application. 287-290
  

Volume 57, Number 6, 25 March 1996

• Angelo Monti:
  On the Computational Complexity of Graph Closures. 291-295
  
• Stanislaw Gawiejnowicz:
  A Note on Scheduling on a Single Processor with Speed Dependent on a Number of Executed Jobs. 297-300
  
• I-Ling Yen:
  A Highly Safe Self-Stabilizing Mutual Exclusion Algorithm. 301-305
  
• Ioannis Fudos, Evaggelia Pitoura, Wojciech Szpankowski:
  On Pattern Occurrences in a Random Text. 307-312
  
• Danny Z. Chen, Kevin S. Klenk:
  Rectilinear Short Path Queries Among Rectangular Obstacles. 313-319
  , Erratum: Inf. Process. Lett. 60(2): 105(1996)
• Sarnath Ramnath, Sivaprakasam Sunder:
  On Two-Processor Scheduling and Maximum Matching in Permutation Graphs. 321-327
  
• Michael Ben-Or, Dana Ron:
  Agreement in the Presence of Faults, on Networks of Bounded Degree. 329-334
  
• Sum-Kwon Kim:
  An Note on Finding Compact Sets in Graphs Represented by an Adjacency List. 335-338