| 1985 | A Bidirectional Shortest-Path Algorithm With Good Average-Case Behavior (Preliminary Version). Michael Luby, Prabhakar Ragde |
| 1985 | A Complete Compositional Model Proof System for a Subset of CCS. Colin Stirling |
| 1985 | A Completeness Theorem for Recursively Defined Types. Mario Coppo |
| 1985 | A Context Dependent Equivalence between Processes. Kim Guldstrand Larsen |
| 1985 | A Fair Protocol for Signing Contracts (Extended Abstract). Michael Ben-Or, Oded Goldreich, Silvio Micali, Ronald L. Rivest |
| 1985 | A Fast Algorithm for Polygon Containment by Translation (Extended Abstract). Steven Fortune |
| 1985 | A Probabilistic Distributed Algorithm for Set Intersection and Its Analysis (Preliminary Version). Thomas G. Kurtz, Udi Manber |
| 1985 | A Simple Proof of the Skolem-Mahler-Lech Theorem. Georges Hansel |
| 1985 | A Universal Domain Technique for Profinite Posets. Carl A. Gunter |
| 1985 | About Rational Sets of Factors of a Bi-Infinite Word. Danièle Beauquier, Maurice Nivat |
| 1985 | Ambiguity and Transcendence. Philippe Flajolet |
| 1985 | An Algebraic Theory of Fair Asynchronous Communicating Processes. Matthew Hennessy |
| 1985 | Applications of an Infinite Squarefree CO-CFL. Michael G. Main, Walter Bucher, David Haussler |
| 1985 | Automata, Languages and Programming, 12th Colloquium, Nafplion, Greece, July 15-19, 1985, Proceedings Wilfried Brauer |
| 1985 | Categorial Combinatory Logic. Pierre-Louis Curien |
| 1985 | Characterization of High Level Tree Transducers. Joost Engelfriet, Heiko Vogler |
| 1985 | Compositionality and Concurrent Networks: Soundness and Completeness of a Proofsystem. Job Zwiers, Willem P. de Roever, Peter van Emde Boas |
| 1985 | Deterministic and Las Vegas Primality Testing Algorithms. Martin Fürer |
| 1985 | Distributed Algorithms in Synchronous Broadcasting Networks (Extended Abstract). Gad M. Landau, Mordechai M. Yung, Zvi Galil |
| 1985 | Do Rational Equivalence Relations have Regular Cross-Sections? J. Howard Johnson |
| 1985 | Dynamic Interpolation Search. Kurt Mehlhorn, Athanasios K. Tsakalidis |
| 1985 | Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract). Harold N. Gabow, Matthias F. M. Stallmann |
| 1985 | Every Commutative Quasirational Language is Regular. Juha Kortelainen |
| 1985 | Finite Group Topology and p-Adic Topology for Free Monoids. Jean-Eric Pin |
| 1985 | Fractional Cascading: A Data Structuring Technique with Geometric Applications. Bernard Chazelle, Leonidas J. Guibas |
| 1985 | Hierarchies of One-Way Multihead Automata Languages. Marek Chrobak |
| 1985 | Hoare's Logic for Nondeterministic Regular Programs: A Nonstandard Completeness Theorem. Maria Teresa Hortalá-González, Mario Rodríguez-Artalejo |
| 1985 | Imposed-Functional Dependencies Inducing Horizontal Decompositions. Paul De Bra |
| 1985 | Infinite Streams and Finite Observations in the Semantics of Uniform Concurrency. J. W. de Bakker, John-Jules Ch. Meyer, Ernst-Rüdiger Olderog |
| 1985 | Linear and Branching Structures in the Semantics and Logics of Reactive Systems. Amir Pnueli |
| 1985 | Lower Bounds by Kolmogorov-Complexity (Extended Abstract). Ming Li |
| 1985 | On Complete Problems for NP$\cap$CoNP. Juris Hartmanis, Neil Immerman |
| 1985 | On Matrix Multiplication Using Array Processors. Peter J. Varman, I. V. Ramakrishnan |
| 1985 | On Probabilistic Time and Space. Hermann Jung |
| 1985 | On Total Regulators Generated by Derivation Relations. Walter Bucher, Andrzej Ehrenfeucht, David Haussler |
| 1985 | On k-Repetition Free Words Generated by Length Uniform Morphisms Over a Binary Alphabet. Veikko Keränen |
| 1985 | On the Use of Relational Expressions in the Design of Efficient Algorithms (Extended Abstract). Seppo Sippu, Eljas Soisalon-Soininen |
| 1985 | Operational Semantics for Order-Sorted Algebra. Joseph A. Goguen, Jean-Pierre Jouannaud, José Meseguer |
| 1985 | Optimal Parallel Pattern Matching in Strings (Extended Summary). Uzi Vishkin |
| 1985 | Optimal Solutions for a Class of Point Retrieval Problems. Bernard Chazelle, Herbert Edelsbrunner |
| 1985 | Partitioning Point Sets in 4 Dimensions. Richard Cole |
| 1985 | Polynomial Levelability and Maximal Complexity Cores. Pekka Orponen, David A. Russo, Uwe Schöning |
| 1985 | Powerdomains as Algebraic Lattices (Preliminary Report). Karel Hrbacek |
| 1985 | Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract). Mark Jerrum |
| 1985 | Repeated Synchronous Snapshots and Their Implementation in CSP (Extended Abstract). Luc Bougé |
| 1985 | Routing Through a Generalized Switchbox. Michael Kaufmann, Kurt Mehlhorn |
| 1985 | Special Relations in Automated Deduction. Zohar Manna, Richard J. Waldinger |
| 1985 | The Complementation Problem for Büchi Automata with Applications to Temporal Logic (Extended Abstract). A. Prasad Sistla, Moshe Y. Vardi, Pierre Wolper |
| 1985 | The Influence of Key Length on the Area-Time Complexity of Sorting. Gianfranco Bilardi, Franco P. Preparata |
| 1985 | The Nearest Neighbor Problem on Bounded Domains. Rolf G. Karlsson, J. Ian Munro, Edward L. Robertson |
| 1985 | Towards a Uniform Topological Treatment of Streams and Functions on Streams. J. W. de Bakker, Joost N. Kok |
| 1985 | Vertex Packing Algorithms. László Lovász |