| 1985 | Do Rational Equivalence Relations have Regular Cross-Sections? | J. Howard Johnson |
| 1985 | Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract). | Mark Jerrum |
| 1985 | Powerdomains as Algebraic Lattices (Preliminary Report). | Karel Hrbacek |
| 1985 | Hoare's Logic for Nondeterministic Regular Programs: A Nonstandard Completeness Theorem. | Maria Teresa Hortal-Gonzlez, Mario Rodrguez-Artalejo |
| 1985 | An Algebraic Theory of Fair Asynchronous Communicating Processes. | Matthew Hennessy |
| 1985 | On Complete Problems for NP$\cap$CoNP. | Juris Hartmanis, Neil Immerman |
| 1985 | A Simple Proof of the Skolem-Mahler-Lech Theorem. | Georges Hansel |
| 1985 | A Universal Domain Technique for Profinite Posets. | Carl A. Gunter |
| 1985 | Operational Semantics for Order-Sorted Algebra. | Joseph A. Goguen, Jean-Pierre Jouannaud, Jos Meseguer |
| 1985 | Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract). | Harold N. Gabow, Matthias F. M. Stallmann |
| 1985 | Deterministic and Las Vegas Primality Testing Algorithms. | Martin Frer |
| 1985 | A Fast Algorithm for Polygon Containment by Translation (Extended Abstract). | Steven Fortune |
| 1985 | Ambiguity and Transcendence. | Philippe Flajolet |
| 1985 | Characterization of High Level Tree Transducers. | Joost Engelfriet, Heiko Vogler |
| 1985 | Categorial Combinatory Logic. | Pierre-Louis Curien |
| 1985 | A Completeness Theorem for Recursively Defined Types. | Mario Coppo |
| 1985 | Partitioning Point Sets in 4 Dimensions. | Richard Cole |
| 1985 | Hierarchies of One-Way Multihead Automata Languages. | Marek Chrobak |
| 1985 | Fractional Cascading: A Data Structuring Technique with Geometric Applications. | Bernard Chazelle, Leonidas J. Guibas |
| 1985 | Optimal Solutions for a Class of Point Retrieval Problems. | Bernard Chazelle, Herbert Edelsbrunner |
| 1985 | On Total Regulators Generated by Derivation Relations. | Walter Bucher, Andrzej Ehrenfeucht, David Haussler |
| 1985 | Imposed-Functional Dependencies Inducing Horizontal Decompositions. | Paul De Bra |
| 1985 | Repeated Synchronous Snapshots and Their Implementation in CSP (Extended Abstract). | Luc Boug |
| 1985 | The Influence of Key Length on the Area-Time Complexity of Sorting. | Gianfranco Bilardi, Franco P. Preparata |
| 1985 | A Fair Protocol for Signing Contracts (Extended Abstract). | Michael Ben-Or, Oded Goldreich, Silvio Micali, Ronald L. Rivest |