| 1981 | A Cook's Tour of Countable Nondeterminism. Krzysztof R. Apt, Gordon D. Plotkin |
| 1981 | A Decision Procedure for the Equivalence of Two DPDAs, One of Which is Linear (Extended Abstract). Yair Itzhaik, Amiram Yehudai |
| 1981 | A New Characterization of the Regular Languages. Christophe Reutenauer |
| 1981 | A Sparse Table Implementation of Priority Queues. Alon Itai, Alan G. Konheim, Michael Rodeh |
| 1981 | A View of Directions in Relational Database Theory. Jeffrey D. Ullman |
| 1981 | Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables. Joos Heintz, Malte Sieveking |
| 1981 | Algebraically Specified Programming Systems and Hoare's Logic. Jan A. Bergstra, John V. Tucker |
| 1981 | Algorithmic Specifications of Abstract Data Types. Jacques Loeckx |
| 1981 | Alternating Multihead Finite Automata (Extended Abstract). K. N. King |
| 1981 | An Axiomatic Approach to the Korenjak-Hopcroft Algorithms. Bruno Courcelle |
| 1981 | Area-Time Optimal VLSI Networks for Computing Integer Multiplications and Discrete Fourier Transform. Franco P. Preparata, Jean Vuillemin |
| 1981 | Automata, Languages and Programming, 8th Colloquium, Acre (Akko), Israel, July 13-17, 1981, Proceedings Shimon Even, Oded Kariv |
| 1981 | Automatic Construction of Verification Condition Generators From Hoare Logics. Mark Moriconi, Richard L. Schwartz |
| 1981 | Characterizing Data Base Dependencies. Johann A. Makowsky |
| 1981 | Chomsky-Schützenberger Representations for Families of Languages and Grammatical Types. Sorin Istrail |
| 1981 | Circular Expressions: Elimination of Static Environments. Ravi Sethi |
| 1981 | Comparing and Putting Together Recursive Path Ordering, Simplification Orderings and Non-Ascending Property for Termination Proofs of Term Rewriting Systems. Alberto Pettorossi |
| 1981 | Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N. Aviezri S. Fraenkel, David Lichtenstein |
| 1981 | Cost Tradeoffs in Graph Embeddings, with Applications (Preliminary Version). Jia-Wei Hong, Kurt Mehlhorn, Arnold L. Rosenberg |
| 1981 | Data Flow Analysis of Applicative Programs. Micha Sharir |
| 1981 | Errata: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory. Johann A. Makowsky |
| 1981 | Finite Models for Deterministic Propositional Dynamic Logic. Mordechai Ben-Ari, Joseph Y. Halpern, Amir Pnueli |
| 1981 | Flow Analysis of Lambda Expressions (Preliminary Version). Neil D. Jones |
| 1981 | Generalized Parikh Mappings and Homomorphisms. Juhani Karhumäki |
| 1981 | Impartiality, Justice and Fairness: The Ethics of Concurrent Termination. Daniel Lehmann, Amir Pnueli, Jonathan Stavi |
| 1981 | Languages reconnaissables et codage prefixe pur. Jean-Eric Pin |
| 1981 | Minimum S-T Cut of a Planar Undirected Network in O(n log²(n)) Time. John H. Reif |
| 1981 | Nondeterminism in Abstract Data Types. P. A. Subrahmanyam |
| 1981 | On LALR(1) Testing. Seppo Sippu, Eljas Soisalon-Soininen |
| 1981 | On Size Bounds for Deterministic Parsers. Esko Ukkonen |
| 1981 | On the (Generalized) Post Correspondence Problem with Lists of Length 2. Andrzej Ehrenfeucht, Grzegorz Rozenberg |
| 1981 | On the Complexity of Simple Arithmetic Expressions. Oscar H. Ibarra, Brian S. Leininger, Shlomo Moran |
| 1981 | On the Density of Color-Families. Emo Welzl |
| 1981 | On the Generation of Cryptographically Strong Pseudo-Random Sequences. Adi Shamir |
| 1981 | Parikh-Bounded Languages. Meera Blattner, Michel Latteux |
| 1981 | Passes, Sweeps and Visits. Joost Engelfriet, Gilberto Filé |
| 1981 | Proving Lower Bounds for Linar Decision Trees. Marc Snir |
| 1981 | Realizing an Equational Specification. Amir Pnueli, R. Zarhi |
| 1981 | Refined Analysis and Improvements on Some Factoring Algorithms. Claus-Peter Schnorr |
| 1981 | Termination of Linear Rewriting Systems (Preliminary Version). Nachum Dershowitz |
| 1981 | The Complexity of Decision Problems for Finite-Turn Multicounter Machines. Eitan M. Gurari, Oscar H. Ibarra |
| 1981 | The Deducibility Problem in Propositional Dynamic Logic. Albert R. Meyer, Robert S. Streett, Grazyna Mirkowska |
| 1981 | The Implication Problem for Data Dependencies. Catriel Beeri, Moshe Y. Vardi |
| 1981 | The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm. Judea Pearl |
| 1981 | Uniform Complexity and Digital Signatures. Karl J. Lieberherr |