| 1990 | The Use of Graphs of Elliptical Influence in Visuel Hierarchical Clustering. | Mirko Krivnek |
| 1990 | Separating +L From L, NL, co-NL and AL (=P) for Oblivious Turing Machines of Linear Access Time. | Matthias Krause |
| 1990 | Interactive Computations of Optimal Solutions. | Jan Krajcek, Pavel Pudlk, Jir Sgall |
| 1990 | On Kleene Algebras and Closed Semirings. | Dexter Kozen |
| 1990 | Vector Language: Simple Description of Hard Instances (Extended Abstract). | Miroslaw Kowaluk, Klaus W. Wagner |
| 1990 | Pumping Lemmas for Tree Languages Generated by Rewrite Systems. | Emmanuel Kounalis |
| 1990 | On the Complexity of Genuinely Polynomial Computation. | Marek Karpinski, Friedhelm Meyer auf der Heide |
| 1990 | Minimal Nontrivial Space Complexity of Probabilistic One-Way Turing Machines. | Janis Kaneps, Rusins Freivalds |
| 1990 | Syntactic Theories. | Jean-Pierre Jouannaud |
| 1990 | A Hierarchy of Compositional Models of I/O-Automata (Extended Abstract). | Bengt Jonsson |
| 1990 | Optimal Algorithms for Dissemination of Information in Some Interconnection Networks (Extended Abstract). | Juraj Hromkovic, Claus-Dieter Jeschke, Burkhard Monien |
| 1990 | The Membership Problem for Context-Free Chain Code Picture Languages. | Friedhelm Hinz |
| 1990 | Dynamic Hashing Strategies. | Friedhelm Meyer auf der Heide |
| 1990 | Specification & Verification of Higher Order Processes. | Michael R. Hansen, Zhou Chaochen |
| 1990 | Tree-Stack Automata. | Wolfgang Golubski, Wolfram-Manfred Lippe |
| 1990 | Quality Criteria for Partial Order Semantics of Place/Transition-Nets. | Robert Gold, Walter Vogler |
| 1990 | Unrestricted Resolution versus N-Resolution. | Andreas Goerdt |
| 1990 | On Possibilities of One-Way Synchronized and Alternating Automata. | Dainis Geidmanis |
| 1990 | Speed-Up Theorem Without Tape Compression. | Viliam Geffert |
| 1990 | A First-Order Logic for Partial Recursive Functions. | Antonio Gavilanes-Franco |
| 1990 | Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract). | Ricard Gavald, Leen Torenvliet, Osamu Watanabe, Jos L. Balczar |
| 1990 | On Checking Versus Evaluation of Multiple Queries. | William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene |
| 1990 | Comparisons Among Classes of Y-Tree Systolic Automata. | Emanuela Fachini, Andrea Maggiolo-Schettini, Davide Sangiorgi |
| 1990 | Query Languages which Express all PTIME Queries for Trees and Unicyclic Graphs. | Pratul Dublish, S. N. Maheshwari |
| 1990 | Event Structures, Causal Trees, and Refinements. | Philippe Darondeau, Pierpaolo Degano |