| 1995 | A New Approach to Analyse Coupled-Context-Free Languages. Günter Hotz, Gisela Pitsch |
| 1995 | A Periodicity Theorem on Words and Applications. Filippo Mignosi, Antonio Restivo, Sergio Salemi |
| 1995 | A Superpolynomial Lower Bound for (1, +k(n))-Branching Programs. Stanislav Zák |
| 1995 | A v-Calculus with Local Views for Systems of Sequential Agents. Peter Niebert |
| 1995 | An Abstract Account of Composition. Martín Abadi, Stephan Merz |
| 1995 | An Elementary Bisimulation Decision Procedure for Arbitrary Context-Free Processes. Olaf Burkart, Didier Caucal, Bernhard Steffen |
| 1995 | An Operator Calculus Approach to the Evolution of Dynamic Data Structures. Philip Feinsilver, René Schott |
| 1995 | Asymptotically Efficient In-Place Merging. Jyrki Katajainen, Tomi Pasanen, George Titan |
| 1995 | Automata That Take Advice. Carsten Damm, Markus Holzer |
| 1995 | Automata for the Modal mu-Calculus and related Results. David Janin, Igor Walukiewicz |
| 1995 | Bridging Across the log(n) Space Frontier. Viliam Geffert |
| 1995 | Comparing Counting Classes for Logspace, One-way Logspace, and First-order. Hans-Jörg Burtschick |
| 1995 | Computational Complexity of Simultaneous Elementary Matching Problems (Extended Abstract). Miki Hermann, Phokion G. Kolaitis |
| 1995 | Decomposable Structures, Boolean Function Representations, and Optimization. Stefan Arnborg |
| 1995 | Derandomization for Sparse Approximations and Independent Sets. Thomas Hofmeister, Hanno Lefmann |
| 1995 | Deterministic Parsing for Augmented Context-free Grammars. Luca Breveglieri, Alessandra Cherubini, Stefano Crespi-Reghizzi |
| 1995 | From Timed Automata to Logic - and Back. François Laroussinie, Kim Guldstrand Larsen, Carsten Weise |
| 1995 | Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete. Osamu Maruyama, Satoru Miyano |
| 1995 | Graph Reducibility of Term Rewriting Systems. M. R. K. Krishna Rao |
| 1995 | Honecomb Networks. Ivan Stojmenovic |
| 1995 | Incremental Model Checking for Decomposable Structures (Extended Abstract). Johann A. Makowsky, Elena V. Ravve |
| 1995 | Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract). Alexander A. Razborov |
| 1995 | Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems. Christoph Meinel, Stephan Waack |
| 1995 | Mathematical Foundations of Computer Science 1995, 20th International Symposium, MFCS'95, Prague, Czech Republic, August 28 - September 1, 1995, Proceedings Jirí Wiedermann, Petr Hájek |
| 1995 | Measure on P: Robustness of the Notion. Eric Allender, Martin Strauss |
| 1995 | Modular Constructions of Distributing Automata. Sébastien Huguet, Antoine Petit |
| 1995 | Multiple Product Modulo Arbitrary Numbers. Claudia Bertram-Kretzberg, Thomas Hofmeister |
| 1995 | Nonuniform Lower Bounds for Exponential Time Classes. Steven Homer, Sarah Mocas |
| 1995 | On Congruences and Partial Orders. Serge Bauget, Paul Gastin |
| 1995 | On a Quantitative Notion of Uniformity. Susanne Kaufmann, Martin Kummer |
| 1995 | On the Complexity of Finite Memory Policies for Markov Decision Processes. Danièle Beauquier, Dima Burago, Anatol Slissenko |
| 1995 | On the Computing Paradigm and Computational Complexity. Juris Hartmanis |
| 1995 | On the Proof Method for Bisimulation (Extended Abstract). Davide Sangiorgi |
| 1995 | Performance Preorder: Ordering Processes with Respect to Speed. Flavio Corradini, Roberto Gorrieri, Marco Roccetti |
| 1995 | Physics and the New Computation. Paul M. B. Vitányi |
| 1995 | Positive Recursive Type Assignment. Pawel Urzyczyn |
| 1995 | Ranked Structures in Nonmonotonic Reasoning and Belief Revision: Abstract. Daniel Lehmann |
| 1995 | Scheduling Parallel Communication: The h-relation Problem. Micah Adler, John W. Byers, Richard M. Karp |
| 1995 | Second Order Logic and the Weak Exponential Hierarchies. Georg Gottlob, Nicola Leone, Helmut Veith |
| 1995 | Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities. Wolfgang Merkle, Yongge Wang |
| 1995 | Solving Cheap Graph Problems an Meshes. Jop F. Sibeyn, Michael Kaufmann |
| 1995 | Some Typical Properties of Large AND/OR Boolean Formulas. Hanno Lefmann, Petr Savický |
| 1995 | String Recognition on Anonymous Rings. Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio |
| 1995 | Strong Lower Bounds on the Approximability of some NPO PB-Complete Maximization Problems. Viggo Kann |
| 1995 | Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages. Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini |
| 1995 | Symbolic Dynamics and Finite Automata. Dominique Perrin |
| 1995 | Syntax and Semantics of Procol. Roel van der Goot, Arie de Bruin |
| 1995 | Synthesizing Distinguishing Formulae for Real Time Systems (Extended Abstract). Jens Chr. Godskesen, Kim Guldstrand Larsen |
| 1995 | The Complexity of Interval Routing on Random Graphs. Michele Flammini, Jan van Leeuwen, Alberto Marchetti-Spaccamela |
| 1995 | The Complexity of the Falsifiability Problem for Pure Implicational Formulas. Peter Heusch |
| 1995 | The Firing Squad Synchronization Problem on Cayley Graphs. Zsuzsanna Róka |
| 1995 | The Hedge: An Efficient Storage Device for Turing Machines with One Head (Extended Abstract). Martin Hühne |
| 1995 | Towards a Calculus of Predicate Transformers. Clare E. Martin |
| 1995 | Towards a Semantic Theory of CML (Extended Abstract). William Ferreira, Matthew Hennessy |
| 1995 | Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract). Sophie Fischer, Lane A. Hemaspaandra, Leen Torenvliet |