| 1994 | A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. Uriel Feige |
| 1994 | A KLeene Theorem for Recognizable Languages over Concurrency Monoids. Manfred Droste |
| 1994 | A Model of Intuitionistic Affine Logic From Stable Domain Theory. Torben Braüner |
| 1994 | A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks. C. Greg Plaxton, Torsten Suel |
| 1994 | A Tight Lower Bound for Primitivity in k-Structures. Paola Bonizzoni |
| 1994 | An Analysis of the Core-ML Language: Expressive Power and Type Reconstruction. Paris C. Kanellakis, Gerd G. Hillebrand, Harry G. Mairson |
| 1994 | Automata, Languages and Programming, 21st International Colloquium, ICALP94, Jerusalem, Israel, July 11-14, 1994, Proceedings Serge Abiteboul, Eli Shamir |
| 1994 | Average-Case Analysis of Pattern-Matching in Trees under the BST Probability Model. José-Ramón Sánchez-Couso, María-Inés Fernández-Camacho |
| 1994 | Bistructures, Bidomains and Linear Logic. Gordon D. Plotkin, Glynn Winskel |
| 1994 | Combining First Order Algebraic Rewriting Systems, Recursion and Extensional Lambda Calculi. Roberto Di Cosmo, Delia Kesner |
| 1994 | Complexity Results for Multi-Pebble Automata and their Logics. Noa Globerman, David Harel |
| 1994 | Deciding Properties of Integral Relational Automata. Karlis Cerans |
| 1994 | Determinizing Asynchronous Automata. Nils Klarlund, Madhavan Mukund, Milind A. Sohoni |
| 1994 | Distribution and Locality of Concurrent Systems. Flavio Corradini, Rocco De Nicola |
| 1994 | Dynamically-Typed Computations for Order-Sorted Equational Presentations. Claus Hintermeier, Claude Kirchner, Hélène Kirchner |
| 1994 | Efficient Local Correctness Checking for Single and Alternating Boolean Equation Systems. Bart Vergauwen, Johan Lewi |
| 1994 | Efficient Strategies for Robot Navigation in Unknown Environment. Aohan Mei, Yoshihide Igarashi |
| 1994 | Equivalences for Fair Kripke Structures. Adnan Aziz, Vigyan Singhal, Felice Balarin, Robert K. Brayton, Alberto L. Sangiovanni-Vincentelli |
| 1994 | Expressiveness of Efficient Semi-Deterministic Choice Constructs. Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht |
| 1994 | Fast Uniform Analysis of Coupled-Context-Free Languages. Günter Hotz, Gisela Pitsch |
| 1994 | Finding Even Cycles Even Faster. Raphael Yuster, Uri Zwick |
| 1994 | Generalized Finiteness Conditions of Labelled Transition Systems. Franck van Breugel |
| 1994 | Higher-Order Process and Their Models. Matthew Hennessy |
| 1994 | Least Solutions of Equations over N. Helmut Seidl |
| 1994 | Liveness in Timed and Untimed Systems. Rainer Gawlick, Roberto Segala, Jørgen F. Søgaard-Andersen, Nancy A. Lynch |
| 1994 | Lower Space Bounds for Randomized Computation. Rusins Freivalds, Marek Karpinski |
| 1994 | Maintaining Spanning Trees of Small Diameter. Giuseppe F. Italiano, Rajiv Ramaswami |
| 1994 | Multiway Cuts in Directed and Node Weighted Graphs. Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis |
| 1994 | On The Computational Power of Probabilistic and Faulty Neural Networks. Hava T. Siegelmann |
| 1994 | On some Relations between Dynamical Systems and Transition Systems. Eugene Asarin, Oded Maler |
| 1994 | On the Approximation of Shortest Common Supersequences and Longest Common Subsequences. Tao Jiang, Ming Li |
| 1994 | On the Complementation of Büchi Asynchronous Cellular Automata. Anca Muscholl |
| 1994 | On the Cost of Recomputing: Tight Bounds on Pebbling with Faults. Yonatan Aumann, Judit Bar-Ilan, Uriel Feige |
| 1994 | On the Cutting Edge of Relativization: The Resource Bounded Injury Method. Harry Buhrman, Leen Torenvliet |
| 1994 | On the Theory of Interconnection Networks for Parallel Computers. Eli Upfal |
| 1994 | Optimal Parallel Algorithms for Prefix Matching. Ramesh Hariharan, S. Muthukrishnan |
| 1994 | Optimal Two-Dimensional Compressed Matching. Amihood Amir, Gary Benson, Martin Farach |
| 1994 | PSPACE-Completeness of Certain Algorithmic Problems on the Subgroups of Free Groups. Jean-Camille Birget, Stuart W. Margolis, John C. Meakin, Pascal Weil |
| 1994 | Polynomial Closure of Group Languages and Open Sets of the Hall Topology. Jean-Eric Pin |
| 1994 | Polynomial Time Analysis of Torodial Periodic Graphs. Franz Höfting, Egon Wanke |
| 1994 | Prefix Codes: Equiprobable Words, Unequal Letter Costs. Mordecai J. Golin, Neal E. Young |
| 1994 | Pumping, Cleaning and Symbolic Constraints Solving. Anne-Cécile Caron, Hubert Comon, Jean-Luc Coquidé, Max Dauchet, Florent Jacquemard |
| 1994 | Randomness in Distributed Protocols. Carlo Blundo, Alfredo De Santis, Ugo Vaccaro |
| 1994 | Reasoning about Programs by Exploiting the Environment. Limor Fix, Fred B. Schneider |
| 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 | Simple Fast Parallel Hashing. Joseph Gil, Yossi Matias |
| 1994 | Tailoring Recursing for Complexity. Erich Grädel, Yuri Gurevich |
| 1994 | The Average Case Complexity of the Parallel Prefix Problem. Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer, Stephan Weis |
| 1994 | The Optimal Alphabetic Tree Problem Revisited. Teresa M. Przytycka, Lawrence L. Larmore |
| 1994 | The Size of an Interwine. Jens Lagergren |
| 1994 | Undecidable Verification Problems for Programs with Unreliable Channels. Parosh Aziz Abdulla, Bengt Jonsson |
| 1994 | Unexpected Upper Bounds on the Complexity of Some Communication Games. Pavel Pudlák |
| 1994 | Valuations and Unambiguity of Languages, with Applications to Fractal Geometry. Henning Fernau, Ludwig Staiger |