| 1991 | A Concluent Reduction for the Lambda-Calculus with Surjective Pairing and Terminal Object. Pierre-Louis Curien, Roberto Di Cosmo |
| 1991 | A Kleene Theorem for Infinite Trace Languages. Paul Gastin, Antoine Petit, Wieslaw Zielonka |
| 1991 | A Parallel Algorithm for Two Processors Precedence Constraint Scheduling. Hermann Jung, Maria J. Serna, Paul G. Spirakis |
| 1991 | A Specialized Completion Procedure for Monadic String-Rewriting Systems Presenting Groups. Klaus Madlener, Paliath Narendran, Friedrich Otto |
| 1991 | Adding Action Refinement to a Finite Process Algebra. Luca Aceto, Matthew Hennessy |
| 1991 | Algorithms for Determining the Smallest Number of Nonterminals (States) Sufficient for Generating (Accepting) a Regular Language. Kosaburo Hashiguchi |
| 1991 | An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem. Zvi Galil, Oded Margalit |
| 1991 | An Efficient NC Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs. Martin Fürer |
| 1991 | An Eilenberg Theorem for Infinity-Languages. Thomas Wilke |
| 1991 | Automata, Languages and Programming, 18th International Colloquium, ICALP91, Madrid, Spain, July 8-12, 1991, Proceedings Javier Leach Albert, Burkhard Monien, Mario Rodríguez-Artalejo |
| 1991 | Average Case Complexity. Yuri Gurevich |
| 1991 | Balancing Order and Chaos in Image Generation (Extended Abstract). Karel Culík II, Simant Dube |
| 1991 | Better Algorithms for the Pathwidth and Treewidth of Graphs. Hans L. Bodlaender, Ton Kloks |
| 1991 | CCS + Time = An Interleaving Model for Real Time Systems. Wang Yi |
| 1991 | Collapsing Degrees via Strong Computation (Extended Abstract). Lane A. Hemachandra, Albrecht Hoene |
| 1991 | Complete Axiomatizations of Some Quotient Term Algebras. Hubert Comon |
| 1991 | Computational Geometry for the Gourmet: Old Fare and New Dishes. Bernard Chazelle |
| 1991 | Computing Behavioural Relations, Logically. Rance Cleaveland, Bernhard Steffen |
| 1991 | Computing Shortest Paths and Distances in Planar Graphs. Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis |
| 1991 | Computing Shortest Transversals. Binay K. Bhattacharya, Godfried T. Toussaint |
| 1991 | Cononical Sets of Horn Clauses. Nachum Dershowitz |
| 1991 | Deciding History Preserving Bisimilarity. Walter Vogler |
| 1991 | Degree and Decomposability of Variable-Length Codes. Véronique Bruyère, Clelia De Felice |
| 1991 | Efficient Algorithms for Path Problems with Gernal Cost Citeria. Thomas Lengauer, Dirk Theune |
| 1991 | Efficient Maximal Cubic Graph Cuts (Extended Abstract). Martin Loebl |
| 1991 | Extensional Embedding of a Strongly Stable Model of PCF. Antonio Bucciarelli, Thomas Ehrhard |
| 1991 | Fast Parallel Generation of Random Permutations. Torben Hagerup |
| 1991 | Finding Minimal Forbidden Minors Using a Finite Congruence. Jens Lagergren, Stefan Arnborg |
| 1991 | General Resolution of Tseitin Formulas is Hard. Jean-Denis Fouks |
| 1991 | Improved Parallel Computations with Matrices and Polynomials. Dario Bini, Luca Gemignani, Victor Y. Pan |
| 1991 | Improving Known Solutions is Hard. Desh Ranjan, Suresh Chari, Pankaj Rohatgi |
| 1991 | L Morphisms: Bounded Delay and Regularity of Ambiguity. Juha Honkala, Arto Salomaa |
| 1991 | Lazard's Factorizations of Free Partially Commutative Monoids. Gérard Duchamp, Daniel Krob |
| 1991 | Logic Programming with Recurrence Domains. Hong Chen, Jieh Hsiang |
| 1991 | Logical and Computational Aspects of Programming with Sets/Bags/Lists. Val Tannen, Ramesh Subrahmanyam |
| 1991 | Maintaining Biconnected Components of Dynamic Planar Graphs. Zvi Galil, Giuseppe F. Italiano |
| 1991 | Minimal NFA Problems Are Hard. Tao Jiang, Bala Ravikumar |
| 1991 | Model-Checking for Probabilistic Real-Time Systems (Extended Abstract). Rajeev Alur, Costas Courcoubetis, David L. Dill |
| 1991 | On Confluent Semi-Commutations - Decidability and Complexity Results. Volker Diekert, Edward Ochmanski, Klaus Reinhardt |
| 1991 | On Linear Decision Trees Computing Boolean Functions. Hans Dietmar Gröger, György Turán |
| 1991 | On Logics, Tilings, and Automata. Wolfgang Thomas |
| 1991 | On the Power of Multiple Reads in a Chip. Pavol Duris, Zvi Galil |
| 1991 | On the Semantics of Logic Programs. Maurizio Gabbrielli, Giorgio Levi |
| 1991 | On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages. Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani |
| 1991 | Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion. R. Ravi, Ajit Agrawal, Philip N. Klein |
| 1991 | Program Checkers for Probability Generation. Sampath Kannan, Andrew Chi-Chih Yao |
| 1991 | Program Composition and Modular Verification. Limor Fix, Nissim Francez, Orna Grumberg |
| 1991 | Provably Recursive Programs and Program Extraction. Tim Fernando |
| 1991 | Ray Shooting in Polygons Using Geodesic Triangulations. Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, John Hershberger, Micha Sharir, Jack Snoeyink |
| 1991 | Running Time to Recognize Nonregular Languages by 2-Way Probabilistic Automata. Janis Kaneps, Rusins Freivalds |
| 1991 | Safety for Branching Time Semantics. Ahmed Bouajjani, Jean-Claude Fernandez, Susanne Graf, Carlos Rodríguez, Joseph Sifakis |
| 1991 | Satisfiability of Systems of Ordinal Notations with the Subterm Property is Decidable. Jean-Pierre Jouannaud, Mitsuhiro Okada |
| 1991 | Static on Random Trees. Rafael Casas, Josep Díaz, Conrado Martinez |
| 1991 | String Matching with Preprocessing of Text and Pattern. Moni Naor |
| 1991 | Strutural Parallel Algorithmics. Uzi Vishkin |
| 1991 | The Expected Extremes in a Delaunay Triangulation. Marshall W. Bern, David Eppstein, F. Frances Yao |
| 1991 | The Expressive Power of Implicit Specifications. Kim Guldstrand Larsen |
| 1991 | The Meaning of Negative Premises in Transition System Specifications. Roland N. Bol, Jan Friso Groote |
| 1991 | The POwer of Reconfiguration. Yosi Ben-Asher, David Peleg, Rajiv Ramaswami, Assaf Schuster |
| 1991 | Two P-Complete Problems in the Theory of the Reals. Felipe Cucker, A. Torrecillas |
| 1991 | Uniform Ideals and Strictness Analysis. Christine Ernoult, Alan Mycroft |