| 1994 | Average-Case Analysis of Pattern-Matching in Trees under the BST Probability Model. | Jos-Ramn Snchez-Couso, Mara-Ins Fernndez-Camacho |
| 1994 | Unexpected Upper Bounds on the Complexity of Some Communication Games. | Pavel Pudlk |
| 1994 | The Optimal Alphabetic Tree Problem Revisited. | Teresa M. Przytycka, Lawrence L. Larmore |
| 1994 | Bistructures, Bidomains and Linear Logic. | Gordon D. Plotkin, Glynn Winskel |
| 1994 | A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks. | C. Greg Plaxton, Torsten Suel |
| 1994 | Polynomial Closure of Group Languages and Open Sets of the Hall Topology. | Jean-Eric Pin |
| 1994 | Short Vertex Disjoint Paths and Multiconnectivity in Random Graphs: Reliable Network Computing. | Sotiris E. Nikoletseas, Krishna V. Palem, Paul G. Spirakis, Moti Yung |
| 1994 | On the Complementation of Bchi Asynchronous Cellular Automata. | Anca Muscholl |
| 1994 | Efficient Strategies for Robot Navigation in Unknown Environment. | Aohan Mei, Yoshihide Igarashi |
| 1994 | The Size of an Interwine. | Jens Lagergren |
| 1994 | Determinizing Asynchronous Automata. | Nils Klarlund, Madhavan Mukund, Milind A. Sohoni |
| 1994 | An Analysis of the Core-ML Language: Expressive Power and Type Reconstruction. | Paris C. Kanellakis, Gerd G. Hillebrand, Harry G. Mairson |
| 1994 | On the Approximation of Shortest Common Supersequences and Longest Common Subsequences. | Tao Jiang, Ming Li |
| 1994 | The Average Case Complexity of the Parallel Prefix Problem. | Andreas Jakoby, Rdiger Reischuk, Christian Schindelhauer, Stephan Weis |
| 1994 | Maintaining Spanning Trees of Small Diameter. | Giuseppe F. Italiano, Rajiv Ramaswami |
| 1994 | Fast Uniform Analysis of Coupled-Context-Free Languages. | Gnter Hotz, Gisela Pitsch |
| 1994 | Polynomial Time Analysis of Torodial Periodic Graphs. | Franz Hfting, Egon Wanke |
| 1994 | Dynamically-Typed Computations for Order-Sorted Equational Presentations. | Claus Hintermeier, Claude Kirchner, Hlne Kirchner |
| 1994 | Higher-Order Process and Their Models. | Matthew Hennessy |
| 1994 | Optimal Parallel Algorithms for Prefix Matching. | Ramesh Hariharan, S. Muthukrishnan |
| 1994 | Expressiveness of Efficient Semi-Deterministic Choice Constructs. | Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht |
| 1994 | Tailoring Recursing for Complexity. | Erich Grdel, Yuri Gurevich |
| 1994 | Prefix Codes: Equiprobable Words, Unequal Letter Costs. | Mordecai J. Golin, Neal E. Young |
| 1994 | Complexity Results for Multi-Pebble Automata and their Logics. | Noa Globerman, David Harel |
| 1994 | Simple Fast Parallel Hashing. | Joseph Gil, Yossi Matias |