Information Processing Letters, Volume 52

Volume 52, Number 1, October 1994

Nakagawa Akinari, Hiroshi Hagiwara: On the Real-Number Representation with Variable-Length Exponent Field. 1-6 BibTeX
Charles U. Martel: Maximum Finding on a Multiple Access Broadcast Network. 7-15 BibTeX
Torben Æ. Mogensen: WORM-2DPDAs: An Extension to 2DPDAs that can be Simulated in Linear Time. 15-22 BibTeX
Md. Mozammel Huq Azad Khan: An Algorithm for Hazard-Free Minimization of Incompletely Specified Switching Function. 23-29 BibTeX
Lawrence L. Larmore, Wojciech Rytter: An Optimal Sublinear Time Parallel Algorithm for Some Dynamic Programming Problems. 31-34 BibTeX
Shao Dong Chen, Hong Shen, Rodney W. Topor: An Efficient Permutation-Based Parallel Range-Join Algorithm on N-Dimensional Torus Computers. 35-38 BibTeX
Jon M. Kleinberg: A Lower Bound for Two-Server Balancing Algorithms. 39-43 BibTeX
Giulia Galbiati, Francesco Maffioli, Angelo Morzenti: A Short Note on the Approximability of the Maximum Leaves Spanning Tree Problem. 45-49 BibTeX
Aohan Mei, Yoshihide Igarashi: An Efficient Strategy for Robot Navigation in Unknown Environment. 51-56 BibTeX

Helmut Seidl: Haskell Overloading is DEXPTIME-Complete. 57-60 BibTeX
Mikael Rittri: Semi-Unification of Two Terms in Abelian Groups. 61-68 BibTeX , Corrigendum: Inf. Process. Lett. 53(4): 235(1995) BibTeX
Bern-Cherng Liaw, Richard C. T. Lee: An Optimal Algorithm to Solve the Minimum Weakly Cooperative Guards Problem for 1-Spiral Polygons. 69-75 BibTeX
Chen-Hsing Peng, Jia-Shung Wang, Richard C. T. Lee: Recognizing Shortest-Path Trees in Linear Time. 77-85 BibTeX
Refael Hassin, Shlomo Lahav: Maximizing the Number of Unused Colors in the Vertex Coloring Problem. 87-90 BibTeX
Takehiro Tokuda, Yoshimichi Watanabe: An Attribute Evaluation of Context-Free Languages. 91-98 BibTeX
Mohamed G. Gouda: Stabilizing Observers. 99-103 BibTeX
Jean Mayo, Phil Kearns: Distributed Termination Detection with Roughly Synchronized Clocks. 105-108 BibTeX
Thomas Roos, Peter Widmayer: k-Violation Linear Programming. 109-114 BibTeX

Alberto Pedrotti: Analysis of a List-Update Strategy. 115-121 BibTeX
Y. Daniel Liang: On the Feedback Vertex Set Problem in Permutation Graphs. 123-129 BibTeX
Kirk Pruhs: Average-Case Scalable On-Line Algorithms for Fault Replacement. 131-136 BibTeX
Irène Durand, Bruno Salinier: Constructor Equivalent Term Rewriting Systems are Strongly Sequential: A Direct Proof. 137-145 BibTeX
Paul F. Dietz, Rajeev Raman: A Constant Update Time Finger Search Tree. 147-154 BibTeX
Luc Devroye, Paul Kruszewski: A Note on the Horton-Strahler Number for Random Trees. 155-159 BibTeX
Frank Wagner: Approximate Map Labeling is in Omega (n log n). 161-165 BibTeX
Michele Flammini: On the Learnability of Monotone k \mu-DNF Formulae Under Product Distributions. 167-173 BibTeX

Rajesh P. N. Rao, Jörg Rothe, Osamu Watanabe: Upward Separation for FewP and Related Classes. 175-180 BibTeX
Ernie Cohen: The Convergence Span of Greedy Load Balancing. 181-182 BibTeX
Chuzo Iwamoto, Godfried T. Toussaint: Finding Hamiltonian Circuits in Arrangements of Jordan Curves is NP-Complete. 183-189 BibTeX
Su-Hyun Lee, Do-Hyung Kim, Kwang-Moo Choe: Path for AND-Parallel Execution of Logic Programs. 191-199 BibTeX
Hung-Min Sun, Shiuh-Pyng Shieh: On Dynamic Threshold Schemes. 201-206 BibTeX
Esko Nuutila: An Efficient Transitive Closure Algorithm for Cyclic Digraphs. 207-213 BibTeX
Mark de Berg, Marc J. van Kreveld: Rectilinear Decompositions with Low Stabbing Number. 215-221 BibTeX
Pierre Kelsen: An Optimal Parallel Algorithm for Maximal Matching. 223-228 BibTeX

H. Petersen: Refined Simulation of Multihead Automata. 229-233 BibTeX
Ronald V. Book: On Collapsing the Polynomial-Time Hierarchy. 235-237 BibTeX
Samir Khuller, Uzi Vishkin: On the Parallel Complexity of Digraph Reachability. 239-241 BibTeX
James F. Korsh: Loopless Generation of k-Ary Tree Sequences. 243-247 BibTeX
Eric T. Bax: Algorithms to Count Paths and Cycles. 249-252 BibTeX
Mark Allen Weiss: Linear-Time Construction of Treaps and Cartesian Trees. 253-257 BibTeX
Jin-Tai Yan, Pei-Yung Hsiao: A Fuzzy Clustering Algorithm for Graph Bisection. 259-263 BibTeX
Zhi-Zhong Chen: A Parallel Algorithm for Finding a Triconnected Component Separator with an Application. 265-271 BibTeX
Zbigniew Duszak, Waldemar W. Koczkodaj: Generalization of a New Definition of Consistency for Pairwise Comparisons. 273-276 BibTeX
Fabrizio Luccio, Alberto Pedrotti: A Parallel List Update Problem. 277-284 BibTeX

Jan A. Bergstra, Gheorghe Stefanescu: Bisimulation is Two-Way Simulation. 285-287 BibTeX
Arturo Carpi: On Repeated Factors in C^\infty-Words. 289-294 BibTeX
Subir Bhattacharya, Amitava Bagchi: A General Framework for Minimax Search in Game Trees. 295-301 BibTeX
Philip N. Klein: A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm. 303-307 BibTeX
Y. Daniel Liang: Dominations in Trapezoid Graphs. 309-315 BibTeX
Jing-Ho Yan, Gerard J. Chang: The Path-Partition Problem in Block Graphs. 317-322 BibTeX
H. Petersen: On the Determinacy Problem for Two-Way Pushdown Automata. 323-324 BibTeX
Luke O'Connor: An Upper Bound on the Number of Functions Satisfying the Strict Avalanche Criterion. 325-327 BibTeX
Ravi B. Boppana: The Decision-Tree Complexity of Element Distinctness. 329-331 BibTeX
Wan Fokkink: A Complete Equational Axiomatization for Prefix Iteration. 333-337 BibTeX
Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini: Corrigendum: An Optimal Lower Bound for Nonregular Languages. 339 BibTeX , ->Inf. Process. Lett. 50(6): 289-292(1994) BibTeX
Erl-Huei Lu, Yi-Chang Cheng, Hsiao-Peng Wuu: Corrigendum: A Complete Decoding Algorithm for Double-Error-Correcting Primitive Binary BCH Codes of Odd m. 341 BibTeX , ->Inf. Process. Lett. 51(3): 117-120(1994) BibTeX