BIT, Volume 32, 1992

This index includes only papers from the Computer Science section of BIT.

Volume 32, Number 1, 1992

Loïc Colson: On List Primitive Recursion and the Complexity of Computing inf. 5-9 BibTeX
Thierry Coquand: The Paradox of Trees in Type Theory. 10-14 BibTeX
Joëlle Despeyroux: Theo: An Interactive Proof Development System. 15-29 BibTeX
Daniel Fredholm, Svetozar Serafimovski: Partial Inductive Definitions as Type-Systems for lambda-Terms. 30-44 BibTeX
Lars Hallnäs: On Systems of Definitions, Induction and Recursion. 45-63 BibTeX
Grigori Mints: Complexity of Subclasses of the Intuitionistic Propositional Calculus. 64-69 BibTeX
Erik Palmgren, Viggo Stoltenberg-Hansen: Remarks on Martin-Löf's Partial Type Theory. 70-83 BibTeX
Anne Salvesen: On Specifications, Subset Types and Interpretation of Proposition in Type Theory. 84-101 BibTeX

Ravi B. Boppana, Magnús M. Halldórsson: Approximating Maximum Independent Sets by Excluding Subgraphs. 180-196 BibTeX
Stefan Arnborg, Andrzej Proskurowski: Canonical Representations of Partial 2- and 3-Trees. 197-214 BibTeX
Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis: Efficient Parallel Algorithms for Shortest Paths in Planar Digraphs. 215-236 BibTeX
David Eppstein: Finding the k Smallest Spanning Trees. 237-248 BibTeX
John Hershberger, Subhash Suri: Applications of a Semi-Dynamic Convex Hull Algorithm. 249-267 BibTeX
Marc J. van Kreveld, Mark H. Overmars, Pankaj K. Agarwal: Intersection Queries in Sets of Disks. 268-279 BibTeX
Christos Levcopoulos, Andrzej Lingas: Fast Algorithms for Greedy Triangulation. 280-296 BibTeX
Ricardo A. Baeza-Yates, Gaston H. Gonnet, Nivio Ziviani: Improved Bounds for the Expected Behaviour of AVL Trees. 297-315 BibTeX
Thomas Papadakis, J. Ian Munro, Patricio V. Poblete: Average Search and Update Costs in Skip Lists. 316-332 BibTeX

Johann Blieberger, Ulrich Schmid: FCFS-Scheduling in a Hard Real-Time Environment Under Rush-Hour Conditions. 370-383 BibTeX
Mamoru Hoshi, Philippe Flajolet: Page Usage in a Quadtree Index. 384-402 BibTeX
Rong-Hong Jan, Lih-Hsing Hsu, Yueh-Ying Lee: The Most Vital Edges with Respect to the Number of Spanning Trees in Two-Terminal Series-Parallel Graphs. 403-412 BibTeX
Mark Levene, George Loizou: Inferring Null Join Dependencies in Relational Databases. 413-429 BibTeX
Harry G. Mairson: The Effect of Table Expansion on the Program Complexity of Perfect Hash Funtions. 430-440 BibTeX

Tung-Shou Chen, Wei-Pang Yang, Richard C. T. Lee: Amortized Analysis of Some Disk Scheduling Algorithms: SSTF, SCAN, and N-Step SCAN. 546-558 BibTeX
Kris Coolsaet, H. De Meyer, Veerle Fack: Optimal Algorithms for Total Exchange without Buffering on the Hypercube. 559-569 BibTeX
Jeannette M. de Graaf, Walter A. Kosters: Expected Heights in Heaps. 570-579 BibTeX
Jyrki Katajainen, Tomi Pasanen: Stable Minimum Space Partitioning in Linear Time. 580-585 BibTeX
Stephan Olariu, James L. Schwing, Jingyuan Zhang: A Constant-Time Channel-Assignment Algorithm on Reconfigurable Meshes. 586-597 BibTeX
A. Louise Perkins: A Mixed Directed-Undirected Data Structure for a Parallel Implementation of a Domain Decomposition Algorithm. 598-608 BibTeX
Chang-Wu Yu, Gen-Huey Chen: The Weighted Maximum Independent Set Problem in Permutation Graphs. 609-618 BibTeX