| 1990 | Nonblocking Graphs: Greedy Algorithms to Compute Disjoint Paths. | Andreas Schwill |
| 1990 | Approximation of Convex Figures by Pairs of Rectangles. | Otfried Schwarzkopf, Ulrich Fuchs, Gnter Rote, Emo Welzl |
| 1990 | On the Construction of Abstract Voronoi Diagrams. | Kurt Mehlhorn, Stefan Meiser, Colm 'Dnlaing |
| 1990 | Hard Promise Problems and Nonuniform Complexity. | Luc Longpr, Alan L. Selman |
| 1990 | Efficient Checking of Computations. | Richard J. Lipton |
| 1990 | Sorting the Sums (xi+yj) in O(n²) Comparisons. | Jean-Luc Lambert |
| 1990 | Updating Almost Complete Trees or One Level Makes All the Difference. | Tony W. Lai, Derick Wood |
| 1990 | Computational Power of One-Way Multihead Finite Automata. | Miroslaw Kutylowski |
| 1990 | Relation-Sorted Algebraic Specifications with Built-in Coercers: Basic Notions and Results. | Hans-Jrg Kreowski, Zhenyu Qian |
| 1990 | Kolmogorov Complexity, Restrited Nondeterminism and Generalized Spectra. | Deborah Joseph, Meera Sitharam |
| 1990 | Combinatorial Rewriting on Traces. | Volker Diekert |
| 1990 | Minimum Vertex Hulls for Polyhedral Domains. | Gautam Das, Deborah Joseph |
| 1990 | Parallel Computations on Strings and Arrays. | Maxime Crochemore, Wojciech Rytter |
| 1990 | Towards a Process Semantics in the Logic Programming Style. | Andrea Corradini, Ugo Montanari |
| 1990 | Semi-Commutations and Algebraic Languages. | Mireille Clerbout, Yves Roos |
| 1990 | Caterpillars and Context-Free Languages. | Michal Chytil, Burkhard Monien |
| 1990 | Playing Games of Incomplete Information. | Jin-yi Cai, Anne Condon, Richard J. Lipton |
| 1990 | Counting Classes: Thresholds, Parity, Mods, and Fewness. | Richard Beigel, John Gill, Ulrich Hertrampf |
| 1990 | Hiding Instances in Multioracle Queries. | Donald Beaver, Joan Feigenbaum |
| 1990 | Minimal Pairs and Complete Problems. | Klaus Ambos-Spies, Steven Homer, Robert I. Soare |
| 1990 | The Ring of k-Regular Sequences. | Jean-Paul Allouche, Jeffrey O. Shallit |
| 1990 | A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. | Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer |
| 1989 | Implementation of a Transition Sematics for Parallel Programs with Shared Variables. | Thomas Wolff |
| 1989 | Some Complexity Theoretic Aspects of AC Rewriting. | Rakesh M. Verma, I. V. Ramakrishnan |
| 1989 | If Deterministic and Nondeterministic Space Complexities are Equal for | Andrzej Szepietowski |