| 1986 | A Compositional Reformulation of Owicki-Gries's Partial Correctness Logic for a Concurrent While Language. Colin Stirling |
| 1986 | A More Efficient Algorithm for Lattice Basis Reduction (Extended Abstract). Claus-Peter Schnorr |
| 1986 | A New Approach to Detection of Locally Indicative Stability. Nir Shavit, Nissim Francez |
| 1986 | A New Duality Result Concerning Voronoi Diagrams. Franz Aurenhammer |
| 1986 | A Parallel Vertex Insertion Algorithm For Minimum Spanning Trees. Peter J. Varman, Kshitij A. Doshi |
| 1986 | A Strong Restriction of the Inductive Completion Procedure. Laurent Fribourg |
| 1986 | A Termination Detector for Static and Dynamic Distributed Systems with Asynchronous Non-first-in-first-out Communication (Extended Abstract). Ten-Hwang Lai |
| 1986 | A Timed Model for Communicating Sequential Processes. George M. Reed, A. W. Roscoe |
| 1986 | A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem. Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson |
| 1986 | A Uniform Reduction Theorem - Extending a Result of J. Grollmann and A. Selman. Kenneth W. Regan |
| 1986 | A Very Fast, Practical Algorithm for Finding a Negative Cycle in a Digraph. Paul G. Spirakis, Athanasios K. Tsakalidis |
| 1986 | Alternating Automata. The Weak Monadic Theory of the Tree, and its Complexity. David E. Muller, Ahmed Saoudi, Paul E. Schupp |
| 1986 | An Improved Algorithm for Transitive Closure on Acyclic Digraphs. Klaus Simon |
| 1986 | Automata, Languages and Programming, 13th International Colloquium, ICALP86, Rennes, France, July 15-19, 1986, Proceedings Laurent Kott |
| 1986 | Characterizations on PUNC and Precomputation (Extended Abstract). Eric Allender |
| 1986 | Classification of all the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial. Amir Averbuch, Shmuel Winograd, Zvi Galil |
| 1986 | Comparison of Algorithms Controlling Concurrent Access to a Database: A Combinatorial Approach. Didier Arquès, Jean Françon, M. T. Guichet, P. Guichet |
| 1986 | Complexity Classes Without Machines: On Complete Languages for UP. Juris Hartmanis, Lane A. Hemachandra |
| 1986 | Containment, Separation, Complete Sets, and Immunity of Complexity Classes. Juris Hartmanis, Ming Li, Yaacov Yesha |
| 1986 | Correspondence between Ternary Simulation and Binary Race Analysis in Gate Networks (Extended Summary). Janusz A. Brzozowski, Carl-Johan H. Seger |
| 1986 | Counting with Rational Functions. Christian Choffrut, Marcel Paul Schützenberger |
| 1986 | Decompositions of Nondeterministic Reductions (Extended Abstract). Klaus-Jörn Lange |
| 1986 | E-Unification Algorithms for a Class of Confluent Term Rewriting Systems. Jia-Huai You, P. A. Subrahmanyam |
| 1986 | Etude Syntaxique des Parties Reconnaissables de Mots Infinis. Jean-Pierre Pécuchet |
| 1986 | Finite Biprefix Sets of Path in a Graph. Clelia De Felice |
| 1986 | Hierarchical Planary Testing Algorithms. Thomas Lengauer |
| 1986 | Intersections of Some Families of Languages. Franz-Josef Brandenburg |
| 1986 | Knowledge, Belief and Time. Sarit Kraus, Daniel Lehmann |
| 1986 | Lower Bounds by Recursion Theoretic Arguments (Extended Abstract). Uwe Schöning |
| 1986 | Lower Bounds for Dynamic Range Query Problems That Permit Subtraction (Extended Abstract). Dan E. Willard |
| 1986 | Min Cut is NP-Complete for Edge Weigthed Trees. Burkhard Monien, Ivan Hal Sudborough |
| 1986 | More Complicated Questions About Maxima and Minima, and Some Closures of NP. Klaus W. Wagner |
| 1986 | On Discerning Words by Automata. Pavel Goralcik, Václav Koubek |
| 1986 | On Exponential Lowness. Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe |
| 1986 | On Fixed-Point Clones (Extended Abstract). Damian Niwinski |
| 1986 | On Nontermination of Knuth-Bendix Algorithm. Miki Hermann, Igor Prívara |
| 1986 | On Recognizable Subsets of Free Partially Commutative Monoids. Yves Métivier |
| 1986 | On The Complexity of Deciding Fair Termination of Probabilistic Concurrent Finite-State Programs. Louis E. Rosier, Hsu-Chun Yen |
| 1986 | Parallel RAMs with Owned Global Memory and Deterministic Context-Free Language Recognition (Extended Abstract). Patrick W. Dymond, Walter L. Ruzzo |
| 1986 | Rational Equivalence Relations. J. Howard Johnson |
| 1986 | Refusal Testing. Iain Phillips |
| 1986 | Semigroups and Languages of Dot-Depth 2. Howard Straubing |
| 1986 | Some Further Results on Digital Search Trees. Peter Kirschenhofer, Helmut Prodinger |
| 1986 | Subpolynomial Complexity Classes of Real Functions and Real Numbers. Norbert Th. Müller |
| 1986 | Synthesis and Equivalence of Concurrent Systems. Björn Lisper |
| 1986 | The Set Union Problem with Backtracking. Heikki Mannila, Esko Ukkonen |
| 1986 | Torsion Matrix Semigroups and Recognizable Transductions. Jean-Paul Mascle |
| 1986 | Tradeoffs for Language Recognition on Parallel Computing Models. Juraj Hromkovic |
| 1986 | Un Algorithme Determinant les Melanges de Deux Mots. Jean-Claude Spehner |