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

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

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

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
Manzur M. 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

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

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

Last update Wed May 22 17:50:09 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page