| 1995 | A Family of Tag Systems for Paperfolding Sequences. Christiane Bercoff |
| 1995 | A Fully Abstract Semantics for Causality in the Pi-Calculus. Michele Boreale, Davide Sangiorgi |
| 1995 | A Packet Routing Protocol for Arbitrary Networks. Friedhelm Meyer auf der Heide, Berthold Vöcking |
| 1995 | A Prossible Code in the Genetic Code. Didier Arquès, Christian J. Michel |
| 1995 | A Random NP-Complete Problem for Inversion of 2D Cellular Automata. Bruno Durand |
| 1995 | A Set-Theoretic Translation Method for (Poly)modal Logics. Giovanna D'Agostino, Angelo Montanari, Alberto Policriti |
| 1995 | Algorithms Explained by Symmetries. Torsten Minkwitz |
| 1995 | Beyond P^(NP) - NEXP. Stephen A. Fenner, Lance Fortnow |
| 1995 | Classes of Bounded Counting Type and their Inclusion Relations. Ulrich Hertrampf |
| 1995 | Coding and Strong Coding in Trace Monoids. Véronique Bruyère, Clelia De Felice |
| 1995 | Communication Complexity of Key Agreement on Small Ranges. Jin-Yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar |
| 1995 | Completeness and Weak Completeness Under Polynomial-Size Circuits. David W. Juedes, Jack H. Lutz |
| 1995 | Computability of Convex Sets (Extended Abstract). Martin Kummer, Marcus Schäfer |
| 1995 | Concurrent Process Equivalences: Some Decision Problems (Abstract). Albert R. Meyer |
| 1995 | Dependence Orders for Computations of Concurrent Automata. Felipe Bracho, Manfred Droste, Dietrich Kuske |
| 1995 | Deterministic Generalized Automata. Dora Giammarresi, Rosa Montalbano |
| 1995 | Dynamic Analysis of the Sizes of Relations. Danièle Gardy, Guy Louchard |
| 1995 | Enumerating Extreme Points in Higher Dimensions. Thomas Ottmann, Sven Schuierer, Subbiah Soundaralakshmi |
| 1995 | Expander Properties in Random Regular Graphs with Edge Faults. Sotiris E. Nikoletseas, Paul G. Spirakis |
| 1995 | Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations. Friedhelm Meyer auf der Heide, Christian Scheideler, Volker Stemann |
| 1995 | Finding Largest Common Embeddable Subtrees. Arvind Gupta, Naomi Nishimura |
| 1995 | Finding the Maximum with Linear Error Probabilities: A Sequential Analysis Approach. Guy Louchard |
| 1995 | Generalized Scans and Tri-Diagonal Systems. Paul F. Fischer, Franco P. Preparata, John E. Savage |
| 1995 | Growing Context-Sensitive Languages and Church-Rosser Languages. Gerhard Buntrock, Friedrich Otto |
| 1995 | Interval Routing Schemes. Michele Flammini, Giorgio Gambosi, Sandro Salomone |
| 1995 | Line Segmentation of Digital Curves in Parallel. Peter Damaschke |
| 1995 | Lower Bounds for Depth-Three Circuits With Equals and Mod-Gates. Frederic Green |
| 1995 | Lower Bounds on Learning Decision Lists and Trees (Extended Abstract). Thomas R. Hancock, Tao Jiang, Ming Li, John Tromp |
| 1995 | Malign Distributions for Average Case Circuit Complexity. Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer |
| 1995 | Normal Numbers and Sources for BPP. Martin Strauss |
| 1995 | On Codings of Traces. Volker Diekert, Anca Muscholl, Klaus Reinhardt |
| 1995 | On Compact Representations of Propositional Circumscription. Marco Cadoli, Francesco M. Donini, Marco Schaerf |
| 1995 | On Realizing Iterated Multiplication by Small Depth Threshold Circuits. Matthias Krause |
| 1995 | On Slender Context-free Languages. Danny Raz |
| 1995 | On the Average Running Time of Odd-Even Merge Sort. Christine Rüb |
| 1995 | On the Separators on an Infinite Word Generated by a Morphism. Emmanuelle Garel |
| 1995 | On the Sizes of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks. Juraj Hromkovic, Krzysztof Lorys, Przemyslawa Kanarek, Ralf Klasing, Walter Unger, Hubert Wagener |
| 1995 | On the Sparse Set Conjecture for Sets with Low Denisty. Harry Buhrman, Montserrat Hermo |
| 1995 | On the Structure of Log-Space Probabilistic Complexity Classes (Extended Abstract). Ioan I. Macarie |
| 1995 | On the Subword Equivalence Problem for Infinite Words. Isabelle Fagnot |
| 1995 | On the Synthesis of Discrete Controllers for Timed Systems (An Extended Abstract). Oded Maler, Amir Pnueli, Joseph Sifakis |
| 1995 | On the Synthesis of Strategies in Infinite Games. Wolfgang Thomas |
| 1995 | On the Undecidability of Deadlock Detection in Families of Nets. Anne-Cécile Fabret, Antoine Petit |
| 1995 | On-line and Dynamic Algorithms for Shorted Path Problems. Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis |
| 1995 | Optimal Average Case Sorting on Arrays. Manfred Kunde, Rolf Niedermeier, Klaus Reinhardt, Peter Rossmanith |
| 1995 | Optimal Lower Bounds on the Multiparty Communication Complexity. Pavol Duris, José D. P. Rolim |
| 1995 | Optimal Simulation of Automata by Neural Nets. Piotr Indyk |
| 1995 | Partial Derivates of Regular Expressions and Finite Automata Constructions. Valentin M. Antimirov |
| 1995 | Pseudorandom Generators and the Frequency of Simplicity. Yenjo Han, Lane A. Hemaspaandra |
| 1995 | Resource-Bounded Instance Complexity (Extended Abstract). Lance Fortnow, Martin Kummer |
| 1995 | STACS 95, 12th Annual Symposium on Theoretical Aspects of Computer Science, Munich, Germany, March 2-4, 1995, Proceedings Ernst W. Mayr, Claude Puech |
| 1995 | Simultaneous Messages vs. Communication. László Babai, Peter G. Kimmel, Satyanarayana V. Lokam |
| 1995 | Structural Complexity of Omega-Automata. Sriram C. Krishnan, Anuj Puri, Robert K. Brayton |
| 1995 | Systolic Tree Omega-Languages. Angelo Monti, Adriano Peron |
| 1995 | The Chi-t-Coloring Problem. Damon Kaller, Arvind Gupta, Thomas C. Shermer |
| 1995 | The Number of Views of Piecewise-Smooth Algebraic Objects. Sylvain Petitjean |
| 1995 | Two-Dimensional Pattern Matching in Linear Time and Small Space. Maxime Crochemore, Leszek Gasieniec, Wojciech Plandowski, Wojciech Rytter |