| 1996 | Linear Dynamic Kahn Networks Are Deterministic. | Arie de Bruin, Shan-Hwei Nienhuys-Cheng |
| 1996 | Bisimilarity Problems Requiring Exponential Time. | Michele Boreale, Luca Trevisan |
| 1996 | A Lambda Calculus of Incomplete Objects. | Viviana Bono, Michele Bugliesi, Luigi Liquori |
| 1996 | On the Query Complexity of Sets. | Richard Beigel, William I. Gasarch, Martin Kummer, Timothy H. McNicholl, Frank Stephan |
| 1996 | Logic of Predicates with Explicit Substitutions. | Marek A. Bednarczyk |
| 1996 | From Specifications to Programs: A Fork-Algebraic Approach to Bridge the Gap. | Gabriel Baum, Marcelo F. Frias, Armando Martin Haeberer, Pablo E. Martnez Lpez |
| 1996 | A Modal Logic for Data Analysis. | Philippe Balbiani |
| 1995 | A Superpolynomial Lower Bound for (1, +k(n))-Branching Programs. | Stanislav Zk |
| 1995 | Physics and the New Computation. | Paul M. B. Vitnyi |
| 1995 | Positive Recursive Type Assignment. | Pawel Urzyczyn |
| 1995 | Honecomb Networks. | Ivan Stojmenovic |
| 1995 | Solving Cheap Graph Problems an Meshes. | Jop F. Sibeyn, Michael Kaufmann |
| 1995 | On the Proof Method for Bisimulation (Extended Abstract). | Davide Sangiorgi |
| 1995 | The Firing Squad Synchronization Problem on Cayley Graphs. | Zsuzsanna Rka |
| 1995 | Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract). | Alexander A. Razborov |
| 1995 | Graph Reducibility of Term Rewriting Systems. | M. R. K. Krishna Rao |
| 1995 | Symbolic Dynamics and Finite Automata. | Dominique Perrin |
| 1995 | A v-Calculus with Local Views for Systems of Sequential Agents. | Peter Niebert |
| 1995 | A Periodicity Theorem on Words and Applications. | Filippo Mignosi, Antonio Restivo, Sergio Salemi |
| 1995 | Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities. | Wolfgang Merkle, Yongge Wang |
| 1995 | Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems. | Christoph Meinel, Stephan Waack |
| 1995 | Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete. | Osamu Maruyama, Satoru Miyano |
| 1995 | Towards a Calculus of Predicate Transformers. | Clare E. Martin |
| 1995 | Incremental Model Checking for Decomposable Structures (Extended Abstract). | Johann A. Makowsky, Elena V. Ravve |
| 1995 | Ranked Structures in Nonmonotonic Reasoning and Belief Revision: Abstract. | Daniel Lehmann |