| 1990 | A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. Eric Allender, Richard Beigel, Ulrich Hertrampf, Steven Homer |
| 1990 | Approximation of Convex Figures by Pairs of Rectangles. Otfried Schwarzkopf, Ulrich Fuchs, Günter Rote, Emo Welzl |
| 1990 | Caterpillars and Context-Free Languages. Michal Chytil, Burkhard Monien |
| 1990 | Combinatorial Rewriting on Traces. Volker Diekert |
| 1990 | Computational Power of One-Way Multihead Finite Automata. Miroslaw Kutylowski |
| 1990 | Counting Classes: Thresholds, Parity, Mods, and Fewness. Richard Beigel, John Gill, Ulrich Hertrampf |
| 1990 | Efficient Checking of Computations. Richard J. Lipton |
| 1990 | Enumerative Combinatorics and Computer Science. Xavier Gérard Viennot |
| 1990 | Failures Semantics Based on Interval Semiwords is a Congruence for Refinement. Walter Vogler |
| 1990 | Hard Promise Problems and Nonuniform Complexity. Luc Longpré, Alan L. Selman |
| 1990 | Hiding Instances in Multioracle Queries. Donald Beaver, Joan Feigenbaum |
| 1990 | Infinite Trees and Automaton Definable Relations over Omega-Words. Wolfgang Thomas |
| 1990 | Kolmogorov Complexity, Restrited Nondeterminism and Generalized Spectra. Deborah Joseph, Meera Sitharam |
| 1990 | Minimal Pairs and Complete Problems. Klaus Ambos-Spies, Steven Homer, Robert I. Soare |
| 1990 | Minimum Vertex Hulls for Polyhedral Domains. Gautam Das, Deborah Joseph |
| 1990 | Nonblocking Graphs: Greedy Algorithms to Compute Disjoint Paths. Andreas Schwill |
| 1990 | On the Construction of Abstract Voronoi Diagrams. Kurt Mehlhorn, Stefan Meiser, Colm Ó'Dúnlaing |
| 1990 | Parallel Computations on Strings and Arrays. Maxime Crochemore, Wojciech Rytter |
| 1990 | Playing Games of Incomplete Information. Jin-Yi Cai, Anne Condon, Richard J. Lipton |
| 1990 | Relation-Sorted Algebraic Specifications with Built-in Coercers: Basic Notions and Results. Hans-Jörg Kreowski, Zhenyu Qian |
| 1990 | STACS 90, 7th Annual Symposium on Theoretical Aspects of Computer Science, Rouen, France, February 22-24, 1990, Proceedings Christian Choffrut, Thomas Lengauer |
| 1990 | Semi-Commutations and Algebraic Languages. Mireille Clerbout, Yves Roos |
| 1990 | Sorting the Sums (xi+yj) in O(n²) Comparisons. Jean-Luc Lambert |
| 1990 | The Analysis of Local Search Problems and Their Heuristics. Mihalis Yannakakis |
| 1990 | The Ring of k-Regular Sequences. Jean-Paul Allouche, Jeffrey O. Shallit |
| 1990 | Towards a Process Semantics in the Logic Programming Style. Andrea Corradini, Ugo Montanari |
| 1990 | Updating Almost Complete Trees or One Level Makes All the Difference. Tony W. Lai, Derick Wood |