| 1995 | On Using Learning Automata for Fast Graph Partitioning. | B. John Oommen, Edward V. de St. Croix |
| 1995 | On Monotonous Oracle Machines. | Martin Mundhenk |
| 1995 | Lower Bounds for the Modular Communication Complexity of Various Graph Accessibility Problems. | Christoph Meinel, Stephan Waack |
| 1995 | Multiple Alignment of Biological Sequences with Gap Flexibility. | Joao Meidanis, Joo C. Setubal |
| 1995 | Cyclic Automata Networks on Finite Graphs. | Martn Matamala, Eric Goles Ch. |
| 1995 | Non-Erasing Turing Machines: A New Frontier Between a Decidable Halting Problem and Universality. | Maurice Margenstern |
| 1995 | Multihead Two-Way probabilistic Finite Automata. | Ioan I. Macarie |
| 1995 | Pushdown Automata with Bounded Nondeterminism and Bounded Anbiguity. | Christian Herzog |
| 1995 | State Complexity of SBTA Languages. | Jozef Gruska, Angelo Monti, Margherita Napoli, Domenico Parente |
| 1995 | On the Complexity of Computing the Greatest Common Divisor of Several Univariate Polynomials. | Laureano Gonzlez-Vega |
| 1995 | Unbounded Search and Recursive Graph Problems. | William I. Gasarch, Katia S. Guimares |
| 1995 | Gauss Periods and Fast Exponentiation in Finite Fields (Extended Abstract). | Shuhong Gao, Joachim von zur Gathen, Daniel Panario |
| 1995 | On the Approximability of some Maximum Spanning Tree Problems. | Giulia Galbiati, Angelo Morzenti, Francesco Maffioli |
| 1995 | On Edge-Colouring Indifference Graphs. | Celina M. H. de Figueiredo, Joo Meidanis, Clia Picinin de Mello |
| 1995 | Paging More Than One Page. | Esteban Feuerstein |
| 1995 | Linear-Time Algorithms for Parametric Minimum Spanning Tree Problems on Planar Graphs. | David Fernndez-Baca, Giora Slutzki |
| 1995 | Nearest Neighbour Graph Realizability is NP-hard. | Peter Eades, Sue Whitesides |
| 1995 | Reversible Cellular Automaton Able to Simulate Any Other Reversible One Using Partitioning Automata. | Jrme Olivier Durand-Lose |
| 1995 | On Linear-Time Alphabet-Independent 2-Dimensional Pattern Matching. | Maxime Crochemore, Wojciech Rytter |
| 1995 | (Probabilistic) Recurrence Realtions Revisited. | Shiva Chaudhuri, Devdatt P. Dubhashi |
| 1995 | On Weak Growing Context-Sensitive Grammars. | Gerhard Buntrock, Gundula Niemann |
| 1995 | Recognizable Sets of Numbers in Nonstandard Bases. | Vronique Bruyre, Georges Hansel |
| 1995 | Off-Line Electronic Cash Based on Secret-Key Certificates. | Stefan Brands |
| 1995 | Lower Bounds for the Matrix Chain Ordering Problem (Extended bstract). | Phillip G. Bradford, Venkatesh Choppella, Gregory J. E. Rawlins |
| 1995 | Free Shuffle Algebras in Language Varieties (Extended Abstract). | Stephen L. Bloom, Zoltn sik |