| 1996 | Partial Order Reduction: Model-Checking Using Representatives. | Doron A. Peled |
| 1996 | Specifying and Verifying Parametric Processes. | Wieslaw Pawlowski, Pawel Paczkowski, Stefan Sokolowski |
| 1996 | On the Equivalence Problem for E-Pattern Languages. | Enno Ohlebusch, Esko Ukkonen |
| 1996 | Linear Time Temporal Logics over Mazurkiewicz Traces. | Madhavan Mukund, P. S. Thiagarajan |
| 1996 | Theory and Practice of Action Semantics. | Peter D. Mosses |
| 1996 | Equations on Trees. | Sabrina Mantaci, Antonio Restivo |
| 1996 | Dynamic Graphs. | Andrea Maggiolo-Schettini, Jzef Winkowski |
| 1996 | Probabilistic Metric Semantics for a Simple Language with Recursion. | Marta Z. Kwiatkowska, Gethin Norman |
| 1996 | Construction of List Homomorphisms by Tupling and Fusion. | Zhenjiang Hu, Hideya Iwasaki, Masato Takeichi |
| 1996 | Causal Testing. | Ursula Goltz, Heike Wehrheim |
| 1996 | Polynomial Automaticity, Context-Free Languages, and Fixed Points of Morphism (Extended Abstract). | Ian Glaister, Jeffrey O. Shallit |
| 1996 | Models of DNA Computation. | Alan Gibbons, Martyn Amos, David A. Hodgson |
| 1996 | Minimizing Congestion of Layouts for ATM Networks with Faulty Links. | Leszek Gasieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc |
| 1996 | (poly(log log n), poly(log log n))-Restricted Verifiers are Unlikely to Exist for Languages in NP. | Dimitris Fotakis, Paul G. Spirakis |
| 1996 | On Unconditional Transfer. | Henning Fernau |
| 1996 | Equational Properties of Iteration in Algebraically Complete Categories. | Zoltn sik, Anna Labella |
| 1996 | Simulation of Specification Statements in Hoare Logic. | Kai Engelhardt, Willem P. de Roever |
| 1996 | Self-Similarity Viewed as a Local Property via Tile Sets. | Bruno Durand |
| 1996 | Code Problems on Traces. | Volker Diekert, Anca Muscholl |
| 1996 | On the Power of Nonconservative PRAM. | Anders Dessmark, Andrzej Lingas |
| 1996 | A Class of Information Logics with a Decidable Validity Problem. | Stphane Demri |
| 1996 | Specification and Verification of Timed Lazy Systems. | Flavio Corradini, Marco Pistore |
| 1996 | Word Level Model Checking (Abstract). | Edmund M. Clarke, Xudong Zhao |
| 1996 | Parallel Alternating-Direction Access Machine. | Bogdan S. Chlebus, Artur Czumaj, Leszek Gasieniec, Miroslaw Kowaluk, Wojciech Plandowski |
| 1996 | Shortest Path Problems with Time Constraints. | X. Cai, Ton Kloks, C. K. Wong |