| 1995 | Bicriteria Network Design Problems. | Madhav V. Marathe, R. Ravi, Ravi Sundaram, S. S. Ravi, Daniel J. Rosenkrantz, Harry B. Hunt III |
| 1995 | Generalized Sturmian Languages. | Luis-Miguel Lopez, Philippe Narbel |
| 1995 | Post Correspondence Problem: Words Possible as Primitive Solutions. | Marjo Lipponen |
| 1995 | On-line Resource Management with Applications to Routing and Scheduling. | Stefano Leonardi, Alberto Marchetti-Spaccamela |
| 1995 | On Determining Optimal Strategies in Pursiut Games in the Plane. | Ngoc-Minh L |
| 1995 | The Algebraic Equivalent of AFL Theory. | Werner Kuich |
| 1995 | New Collapse Consequences of NP Having Small Circuits. | Johannes Kbler, Osamu Watanabe |
| 1995 | Graphbots: Mobility in Discrete Spaces. | Samir Khuller, Ehud Rivlin, Azriel Rosenfeld |
| 1995 | Variable-Length Codes for Error Correction. | Helmut Jrgensen, Stavros Konstantinidis |
| 1995 | The Expressive Power of Clocks. | Thomas A. Henzinger, Peter W. Kopke, Howard Wong-Toi |
| 1995 | Hybrid Automata with Finite Bisimulatioins. | Thomas A. Henzinger |
| 1995 | Approximating Minimum Cuts under Insertions. | Monika Rauch Henzinger |
| 1995 | Compactness of Systems of Equations in Semigroups. | Tero Harju, Juhani Karhumki, Wojciech Plandowski |
| 1995 | The PushDown Method to Optimize Chain Logic Programs (Extended Abstract). | Sergio Greco, Domenico Sacc, Carlo Zaniolo |
| 1995 | A Dynamic Programming Algorithm for Constructing Optimal Refix-Free Codes for Unequal Letter Costs. | Mordecai J. Golin, Gnter Rote |
| 1995 | On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications. | Raffaele Giancarlo, Roberto Grossi |
| 1995 | Lower Time Bounds for Randomized Computation. | Rusins Freivalds, Marek Karpinski |
| 1995 | Measure, Category and Learning Theory. | Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan |
| 1995 | Weakly Useful Sequences. | Stephen A. Fenner, Jack H. Lutz, Elvira Mayordomo |
| 1995 | Nonfinite Axiomatizability of the Equational Theory of Shuffle. | Zoltn sik, Michael Bertol |
| 1995 | Theory of 2-Structures. | Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg |
| 1995 | Sensing Versus Nonsensing Automata. | Pavol Duris, Zvi Galil |
| 1995 | A Domain for Concurrent Termination: A Generalization of Mazurkiewicz Traces (Extended Abstract). | Volker Diekert, Paul Gastin |
| 1995 | Causality for Mobile Processes. | Pierpaolo Degano, Corrado Priami |
| 1995 | Implicit Definability and Infinitary Logic in Finite Model Theory. | Anuj Dawar, Lauri Hella, Phokion G. Kolaitis |