| 1999 | Deciding First-Order Properties of Locally Tree-Decomposalbe Graphs. | Markus Frick, Martin Grohe |
| 1999 | Partially Ordered Regular Languages for Graph Queries. | Sergio Flesca, Sergio Greco |
| 1999 | Two-Way Finite State Transducers and Monadic Second-Order Logic. | Joost Engelfriet, Hendrik Jan Hoogeboom |
| 1999 | Numerical Integration with Exact Real Arithmetic. | Abbas Edalat, Marko Krznaric |
| 1999 | Boundedness of Reset P/T Nets. | Catherine Dufourd, Petr Jancar, Philippe Schnoebelen |
| 1999 | Space Time Tradeoffs for Graph Properties. | Yevgeniy Dodis, Sanjeev Khanna |
| 1999 | Timed Alternating Tree Automata: The Automata-Theoretic Solution to the TCTL Model Checking Problem. | Martin Dickhfer, Thomas Wilke |
| 1999 | Real Computations with Fake Numbers. | Felipe Cucker |
| 1999 | Text Compression Using Antidictionaries. | Maxime Crochemore, Filippo Mignosi, Antonio Restivo, Sergio Salemi |
| 1999 | Type Structure for Low-Level Programming Languages. | Karl Crary, J. Gregory Morrisett |
| 1999 | Decidable Fragments of Simultaneous Rigid Reachability. | Vronique Cortier, Harald Ganzinger, Florent Jacquemard, Margus Veanes |
| 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 | Mobility Types for Mobile Ambients. | Luca Cardelli, Andrew D. Gordon, Giorgio Ghelli |
| 1999 | Wide Area Computation. | Luca Cardelli |
| 1999 | New Applications of the Incompressibility Method. | Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitnyi |
| 1999 | A Model for Associative Memory, a Basis for Thinking and Consciousness. | N. G. de Bruijn |
| 1999 | Decomposition and Composition of Timed Automata. | Patricia Bouyer, Antoine Petit |
| 1999 | On Some Tighter Inapproximability Results (Extended Abstract). | Piotr Berman, Marek Karpinski |
| 1999 | General Morphisms of Petri Nets (Extended Abstract). | Marek A. Bednarczyk, Andrzej M. Borzyszkowski |
| 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 | Parametric Temporal Logic for "Model Measuring". | Rajeev Alur, Kousha Etessami, Salvatore La Torre, Doron A. Peled |
| 1999 | Communicating Hierarchical State Machines. | Rajeev Alur, Sampath Kannan, Mihalis Yannakakis |
| 1999 | Bounded Depth Arithmetic Circuits: Counting and Closure. | Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh |
| 1999 | Generating Hard Instances of the Short Basis Problem. | Mikls Ajtai |