| 1999 | A Connection between the Star Problem and the Finite Power Property in Trace Monoids. Daniel Kirsten |
| 1999 | A Framework for Decidable Metrical Logics. Yoram Hirshfeld, Alexander Moshe Rabinovich |
| 1999 | A Model for Associative Memory, a Basis for Thinking and Consciousness. N. G. de Bruijn |
| 1999 | A Variant of the Arrow Distributed Directory with Low Average Complexity. David Peleg, Eilon Reshef |
| 1999 | Accessing Multiple Sequences Through Set Associative Caches. Peter Sanders |
| 1999 | An FPTAS for Agreeably Weighted Variance on a Single Machine. Gerhard J. Woeginger |
| 1999 | Approximation Results for Kinetic Variants of TSP. Mikael Hammar, Bengt J. Nilsson |
| 1999 | Approximations by OBDDs and the Variable Ordering Problem. Matthias Krause, Petr Savický, Ingo Wegener |
| 1999 | Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings Jirí Wiedermann, Peter van Emde Boas, Mogens Nielsen |
| 1999 | Automata, Power Series, and Coinduction: Taking Input Derivatives Seriously. Jan J. M. M. Rutten |
| 1999 | Average-Case Complexity of Shellsort. Tao Jiang, Ming Li, Paul M. B. Vitányi |
| 1999 | Bisimulation Equivanlence Is Decidable for Normed Process Algebra. Yoram Hirshfeld, Mark Jerrum |
| 1999 | Bounded Depth Arithmetic Circuits: Counting and Closure. Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh |
| 1999 | Boundedness of Reset P/T Nets. Catherine Dufourd, Petr Jancar, Philippe Schnoebelen |
| 1999 | Closed Freyd- and kappa-categories. John Power, Hayo Thielecke |
| 1999 | Communicating Hierarchical State Machines. Rajeev Alur, Sampath Kannan, Mihalis Yannakakis |
| 1999 | Compact Routing Tables for Graphs of Bounded Genus. Cyril Gavoille, Nicolas Hanusse |
| 1999 | Comparison of Process Algebra Equivalences Using Formats. Vashti Galpin |
| 1999 | Computing LOGCFL Certificates. Georg Gottlob, Nicola Leone, Francesco Scarcello |
| 1999 | DNA Computing: New Ideas and Paradigms. Grzegorz Rozenberg, Arto Salomaa |
| 1999 | Decidable Fragments of Simultaneous Rigid Reachability. Véronique Cortier, Harald Ganzinger, Florent Jacquemard, Margus Veanes |
| 1999 | Deciding First-Order Properties of Locally Tree-Decomposalbe Graphs. Markus Frick, Martin Grohe |
| 1999 | Decomposition and Composition of Timed Automata. Patricia Bouyer, Antoine Petit |
| 1999 | Distributed Probabilistic Polling and Applications to Proportionate Agreement. Yehuda Hassin, David Peleg |
| 1999 | Efficient Merging, Construction, and Maintenance of Evolutionary Trees. Andrzej Lingas, Hans Olsson, Anna Östlin |
| 1999 | Efficient Techniques for Maintaining Multidimensional Keys in Linked Data Structures. Roberto Grossi, Giuseppe F. Italiano |
| 1999 | Erratum: Bulk-synchronous Parallel Multiplication of Boolean Matrices. Alexandre Tiskin |
| 1999 | Finite Automata with Generalized Acceptance Criteria. Timo Peichl, Heribert Vollmer |
| 1999 | Formalizing a Lazy Substitution Proof System for µ-calculus in the Calculus of Inductive Constructions. Marino Miculan |
| 1999 | From Computational Learning Theory to Discovery Science. Osamu Watanabe |
| 1999 | General Morphisms of Petri Nets (Extended Abstract). Marek A. Bednarczyk, Andrzej M. Borzyszkowski |
| 1999 | Generating Hard Instances of the Short Basis Problem. Miklós Ajtai |
| 1999 | Leader Election by d Dimensional Cellular Automata. Codrin M. Nichitiu, Eric Rémila |
| 1999 | Linear-Time Construction of Two-Dimensional Suffix Trees. Dong Kyue Kim, Kunsoo Park |
| 1999 | Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time. Rasmus Pagh |
| 1999 | Many-Valued Logics and Holographic Proofs. Mario Szegedy |
| 1999 | Mobility Types for Mobile Ambients. Luca Cardelli, Andrew D. Gordon, Giorgio Ghelli |
| 1999 | New Applications of the Incompressibility Method. Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi |
| 1999 | New Upper Bounds for MaxSat. Rolf Niedermeier, Peter Rossmanith |
| 1999 | Non-Interactive Zero-Knowledge: A Low-Randomness Characterization of NP. Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano |
| 1999 | Numerical Integration with Exact Real Arithmetic. Abbas Edalat, Marko Krznaric |
| 1999 | Observations about the Nature and State of Computer Science (Keynote Address). Juris Hartmanis |
| 1999 | On Some Tighter Inapproximability Results (Extended Abstract). Piotr Berman, Marek Karpinski |
| 1999 | On the Complements of Partial k-Trees. Arvind Gupta, Damon Kaller, Thomas C. Shermer |
| 1999 | On the Complexity and Inapproximability of Shortest Implicant Problems. Christopher Umans |
| 1999 | On the Power of Las Vegas II. Two-Way Finite Automata. Juraj Hromkovic, Georg Schnitger |
| 1999 | Online Data Structures in External Memory. Jeffrey Scott Vitter |
| 1999 | Parametric Temporal Logic for "Model Measuring". Rajeev Alur, Kousha Etessami, Salvatore La Torre, Doron A. Peled |
| 1999 | Partially Ordered Regular Languages for Graph Queries. Sergio Flesca, Sergio Greco |
| 1999 | Polynomial and Rational Evaluation and Interpolation (with Structured Matrices). Vadim Olshevsky, Victor Y. Pan |
| 1999 | Proof Techniques for Cryptographic Protocols. Kevin J. Compton, Scott D. Dexter |
| 1999 | Protein Folding, the Levinthal Paradox and Rapidly Mixing Markov Chains. Peter Clote |
| 1999 | Real Computations with Fake Numbers. Felipe Cucker |
| 1999 | Relations between Local and Global Periodicity of Words. Arto Lepistö |
| 1999 | Shortest Anisotropic Paths on Terrains. Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack |
| 1999 | Simulation Preorder on Simple Process Algebras. Antonín Kucera, Richard Mayr |
| 1999 | Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs. Alexander E. Andreev, Juri L. Baskakov, Andrea E. F. Clementi, José D. P. Rolim |
| 1999 | Solos in Concert. Cosimo Laneve, Björn Victor |
| 1999 | Space Time Tradeoffs for Graph Properties. Yevgeniy Dodis, Sanjeev Khanna |
| 1999 | Stable Marriage with Incomplete Lists and Ties. Kazuo Iwama, David F. Manlove, Shuichi Miyazaki, Yasufumi Morita |
| 1999 | T(A) = T(B)? Géraud Sénizergues |
| 1999 | Text Compression Using Antidictionaries. Maxime Crochemore, Filippo Mignosi, Antonio Restivo, Sergio Salemi |
| 1999 | The Wave Propagator Is Turing Computable. Klaus Weihrauch, Ning Zhong |
| 1999 | Timed Alternating Tree Automata: The Automata-Theoretic Solution to the TCTL Model Checking Problem. Martin Dickhöfer, Thomas Wilke |
| 1999 | Two Techniques in the Area of the Star Problem. Daniel Kirsten, Jerzy Marcinkowski |
| 1999 | Two-Way Finite State Transducers and Monadic Second-Order Logic. Joost Engelfriet, Hendrik Jan Hoogeboom |
| 1999 | Type Structure for Low-Level Programming Languages. Karl Crary, J. Gregory Morrisett |
| 1999 | Typed Exeptions and Continuations Cannot Macro-Express Each Other. Jon G. Riecke, Hayo Thielecke |
| 1999 | Wide Area Computation. Luca Cardelli |