| 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 | A Class of Information Logics with a Decidable Validity Problem. Stéphane Demri |
| 1996 | A Lambda Calculus of Incomplete Objects. Viviana Bono, Michele Bugliesi, Luigi Liquori |
| 1996 | A Modal Logic for Data Analysis. Philippe Balbiani |
| 1996 | A Semantic Matching Algorithm: Analysis and Implementation. Hui Shi |
| 1996 | A Sequent Calculus for Subtyping Polymorphic Types. Jerzy Tiuryn |
| 1996 | A Uniform Analysis of Trie Structures that Store Prefixing-Keys with Application to Doubly-Chained Prefixing-Tries. Pilar de la Torre, David T. Kao |
| 1996 | Approximating Good Simultaneous Diophantine Approximations Is Almost NP-Hard. Carsten Rössner, Jean-Pierre Seifert |
| 1996 | Bisimilarity Problems Requiring Exponential Time. Michele Boreale, Luca Trevisan |
| 1996 | Causal Testing. Ursula Goltz, Heike Wehrheim |
| 1996 | Code Problems on Traces. Volker Diekert, Anca Muscholl |
| 1996 | Construction of List Homomorphisms by Tupling and Fusion. Zhenjiang Hu, Hideya Iwasaki, Masato Takeichi |
| 1996 | Dynamic Graphs. Andrea Maggiolo-Schettini, Józef Winkowski |
| 1996 | Equational Properties of Iteration in Algebraically Complete Categories. Zoltán Ésik, Anna Labella |
| 1996 | Equations on Trees. Sabrina Mantaci, Antonio Restivo |
| 1996 | From Specifications to Programs: A Fork-Algebraic Approach to Bridge the Gap. Gabriel Baum, Marcelo F. Frias, Armando Martin Haeberer, Pablo E. Martínez López |
| 1996 | From Static to Dynamic Abstract Data-Types. Elena Zucca |
| 1996 | Kolmogorov Complexity: Recent Research in Moscow. Vladimir A. Uspensky |
| 1996 | Linear Dynamic Kahn Networks Are Deterministic. Arie de Bruin, Shan-Hwei Nienhuys-Cheng |
| 1996 | Linear Time Temporal Logics over Mazurkiewicz Traces. Madhavan Mukund, P. S. Thiagarajan |
| 1996 | Logic of Predicates with Explicit Substitutions. Marek A. Bednarczyk |
| 1996 | Mathematical Foundations of Computer Science 1996, 21st International Symposium, MFCS'96, Cracow, Poland, September 2-6, 1996, Proceedings Wojciech Penczek, Andrzej Szalas |
| 1996 | Mind the Gap! Abstract Versus Concrete Models of Specifications. Donald Sannella, Andrzej Tarlecki |
| 1996 | Minimizing Congestion of Layouts for ATM Networks with Faulty Links. Leszek Gasieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc |
| 1996 | Models of DNA Computation. Alan Gibbons, Martyn Amos, David A. Hodgson |
| 1996 | Nonmonotonic Rule Systems: Foward Chaining, Constraints, and Complexity (Abstract). Jeffrey B. Remmel |
| 1996 | On Fairness in Terminating and Reactive Programs. Axel Wabenhorst |
| 1996 | On Saturation with Flexible Function Symbols. Regimantas Pliuskevicius |
| 1996 | On Unconditional Transfer. Henning Fernau |
| 1996 | On the Conjugation of Standard Morphisms. Patrice Séébold |
| 1996 | On the Equivalence Problem for E-Pattern Languages. Enno Ohlebusch, Esko Ukkonen |
| 1996 | On the Power of Nonconservative PRAM. Anders Dessmark, Andrzej Lingas |
| 1996 | On the Query Complexity of Sets. Richard Beigel, William I. Gasarch, Martin Kummer, Timothy H. McNicholl, Frank Stephan |
| 1996 | Parallel Alternating-Direction Access Machine. Bogdan S. Chlebus, Artur Czumaj, Leszek Gasieniec, Miroslaw Kowaluk, Wojciech Plandowski |
| 1996 | Partial Order Reduction: Model-Checking Using Representatives. Doron A. Peled |
| 1996 | Polynomial Automaticity, Context-Free Languages, and Fixed Points of Morphism (Extended Abstract). Ian Glaister, Jeffrey O. Shallit |
| 1996 | Polynomial Time Samplable Distributions. Tomoyuki Yamakami |
| 1996 | Probabilistic Metric Semantics for a Simple Language with Recursion. Marta Z. Kwiatkowska, Gethin Norman |
| 1996 | Routing on Triangles, Tori and Honeycombs. Jop F. Sibeyn |
| 1996 | Self-Similarity Viewed as a Local Property via Tile Sets. Bruno Durand |
| 1996 | Shortest Path Problems with Time Constraints. X. Cai, Ton Kloks, C. K. Wong |
| 1996 | Simulation of Specification Statements in Hoare Logic. Kai Engelhardt, Willem P. de Roever |
| 1996 | Specification and Verification of Timed Lazy Systems. Flavio Corradini, Marco Pistore |
| 1996 | Specifying and Verifying Parametric Processes. Wieslaw Pawlowski, Pawel Paczkowski, Stefan Sokolowski |
| 1996 | Theory and Practice of Action Semantics. Peter D. Mosses |
| 1996 | Word Level Model Checking (Abstract). Edmund M. Clarke, Xudong Zhao |