| 1991 | Tight RNC Approximations to Max Flow. | Maria J. Serna, Paul G. Spirakis |
| 1991 | An Observational Subset of First-Order Logic Cannot Specify the Behaviour of a Counter (Extended Abstract). | Oliver Schoett |
| 1991 | On the Power of Several Queues. | Martin Schmidt |
| 1991 | Optimal Tradeoffs Between Time And Bit Complexity In Distributed Synchronous Rings. | Bernd Schmeltz |
| 1991 | Tight Bounds on the Path Length of Binary Trees. | Alfredo De Santis, Giuseppe Persiano |
| 1991 | Polynomial Size Constant Depth Circuits with a Limited Number of Negations. | Miklos Santha, Christopher B. Wilson |
| 1991 | Complexity Classification of Truth Maintenance Systems. | Vladislav Rutenburg |
| 1991 | l-Occurrences of Avoidable Patterns. | Peter Roth |
| 1991 | The Owner Concept for PRAMs. | Peter Rossmanith |
| 1991 | Algebraic Program Interpreter APREX2. | D. Rayko, Kirill Vershinin, Igor Romanenko |
| 1991 | Constant Queue Routing on a Mesh. | Sanguthevar Rajasekaran, Richard Overholt |
| 1991 | Optimal Parallel Recognition of Bracket Languages on Hypercubes. | Gisela Pitsch, Elmar Schmer |
| 1991 | A Placement System for Constrained Blocks with Flexible Shapes. | Simone Pimont |
| 1991 | Decidable Sentences for Context-Free Groups. | Klaus Madlener, Friedrich Otto |
| 1991 | Polymorphism, Parameterization and Typing: An Algebraic Specification Perspective. | Jacek Leszczylowski, Martin Wirsing |
| 1991 | IPG - An Interactive Parser Generator. | Jrg Krger, Lothar Schmitz |
| 1991 | Executable Higher-Order Algebraic Specifications. | Jean-Pierre Jouannaud |
| 1991 | Prototype of a Verification Tool. | Thierry Jron |
| 1991 | Testing for Unboundedness of FIFO Channels. | Thierry Jron |
| 1991 | The PROSPECTRA System. | Berthold Hoffmann, Bernd Krieg-Brckner |
| 1991 | The Random Testability of the n-Input AND Gate. | Joachim Hartmann |
| 1991 | On Aperiodic Trace Languages. | Giovanna Guaiana, Antonio Restivo, Sergio Salemi |
| 1991 | The Expressive Power of Second Order Horn Logic. | Erich Grdel |
| 1991 | A Natural Metric for Curves - Computing the Distance for Polygonal Chains and Approximation Algorithms. | Michael Godau |
| 1991 | Decision Problems for Term Rewriting Systems and Recognizable Tree Languages. | Rmi Gilleron |