| 1996 | DATALOG SIRUPs Uniform Boundedness is Undecidable. | Jerzy Marcinkowski |
| 1996 | Relating Word and Tree Automata. | Orna Kupferman, Shmuel Safra, Moshe Y. Vardi |
| 1996 | On the Expressive Power of Variable-Confined Logics. | Phokion G. Kolaitis, Moshe Y. Vardi |
| 1996 | More About Recursive Structures: Descriptive Complexity and Zero-One Laws. | Tirza Hirst, David Harel |
| 1996 | On the Expressive Power of Simply Typed and Let-Polymorphic Lambda Calculi. | Gerd G. Hillebrand, Paris C. Kanellakis |
| 1996 | The Theory of Hybrid Automata. | Thomas A. Henzinger |
| 1996 | Symbolic Protocol Verification With Queue BDDs. | Patrice Godefroid, David E. Long |
| 1996 | A Fully-Abstract Model for the pi-Calculus (Extended Abstract). | Marcelo P. Fiore, Eugenio Moggi, Davide Sangiorgi |
| 1996 | An Until Hierarchy for Temporal Logic. | Kousha Etessami, Thomas Wilke |
| 1996 | Integration in Real PCF. | Abbas Edalat, Martn Htzel Escard |
| 1996 | The Scott Topology Induces the Weak Topology. | Abbas Edalat |
| 1996 | Decidability Problems for the Prenex Fragment of Intuitionistic Logic. | Anatoli Degtyarev, Andrei Voronkov |
| 1996 | Simultaneous E-Unification and Related Algorithmic Problems. | Anatoli Degtyarev, Yuri V. Matiyasevich, Andrei Voronkov |
| 1996 | A Temporal-Logic Approach to Binding-Time Analysis. | Rowan Davies |
| 1996 | Game Semantics & Abstract Machines. | Vincent Danos, Hugo Herbelin, Laurent Regnier |
| 1996 | A Linear Logical Framework. | Iliano Cervesato, Frank Pfenning |
| 1996 | Higher Dimensional Transition Systems. | Gian Luca Cattani, Vladimiro Sassone |
| 1996 | The Essence of Parallel Algol. | Stephen D. Brookes |
| 1996 | Efficient Model Checking via the Equational µ-Calculus. | Girish Bhat, Rance Cleaveland |
| 1996 | Completing Partial Combinatory Algebras With Unique Head-Normal Forms. | Inge Bethke, Jan Willem Klop, Roel C. de Vrijer |
| 1996 | Linear Logic, Monads and the Lambda Calculus. | P. N. Benton, Philip Wadler |
| 1996 | On the Structure of Queries in Constraint Query Languages. | Michael Benedikt, Leonid Libkin |
| 1996 | Complexity Analysis Based on Ordered Resolution. | David A. Basin, Harald Ganzinger |
| 1996 | Subtyping Dependent Types (Summary). | David Aspinall, Adriana B. Compagnoni |
| 1996 | Model-Checking of Correctness Conditions for Concurrent Objects. | Rajeev Alur, Kenneth L. McMillan, Doron A. Peled |