| 1991 | On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages. | Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani |
| 1991 | Program Checkers for Probability Generation. | Sampath Kannan, Andrew Chi-Chih Yao |
| 1991 | Running Time to Recognize Nonregular Languages by 2-Way Probabilistic Automata. | Janis Kaneps, Rusins Freivalds |
| 1991 | A Parallel Algorithm for Two Processors Precedence Constraint Scheduling. | Hermann Jung, Maria J. Serna, Paul G. Spirakis |
| 1991 | Satisfiability of Systems of Ordinal Notations with the Subterm Property is Decidable. | Jean-Pierre Jouannaud, Mitsuhiro Okada |
| 1991 | Minimal NFA Problems Are Hard. | Tao Jiang, Bala Ravikumar |
| 1991 | L Morphisms: Bounded Delay and Regularity of Ambiguity. | Juha Honkala, Arto Salomaa |
| 1991 | Collapsing Degrees via Strong Computation (Extended Abstract). | Lane A. Hemachandra, Albrecht Hoene |
| 1991 | Algorithms for Determining the Smallest Number of Nonterminals (States) Sufficient for Generating (Accepting) a Regular Language. | Kosaburo Hashiguchi |
| 1991 | Fast Parallel Generation of Random Permutations. | Torben Hagerup |
| 1991 | Average Case Complexity. | Yuri Gurevich |
| 1991 | On Linear Decision Trees Computing Boolean Functions. | Hans Dietmar Grger, Gyrgy Turn |
| 1991 | A Kleene Theorem for Infinite Trace Languages. | Paul Gastin, Antoine Petit, Wieslaw Zielonka |
| 1991 | An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem. | Zvi Galil, Oded Margalit |
| 1991 | Maintaining Biconnected Components of Dynamic Planar Graphs. | Zvi Galil, Giuseppe F. Italiano |
| 1991 | On the Semantics of Logic Programs. | Maurizio Gabbrielli, Giorgio Levi |
| 1991 | An Efficient NC Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs. | Martin Frer |
| 1991 | General Resolution of Tseitin Formulas is Hard. | Jean-Denis Fouks |
| 1991 | Program Composition and Modular Verification. | Limor Fix, Nissim Francez, Orna Grumberg |
| 1991 | Provably Recursive Programs and Program Extraction. | Tim Fernando |
| 1991 | Uniform Ideals and Strictness Analysis. | Christine Ernoult, Alan Mycroft |
| 1991 | On the Power of Multiple Reads in a Chip. | Pavol Duris, Zvi Galil |
| 1991 | Lazard's Factorizations of Free Partially Commutative Monoids. | Grard Duchamp, Daniel Krob |
| 1991 | Computing Shortest Paths and Distances in Planar Graphs. | Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis |
| 1991 | On Confluent Semi-Commutations - Decidability and Complexity Results. | Volker Diekert, Edward Ochmanski, Klaus Reinhardt |