8. ICALP 1981: Acre (Akko), Israel

Session 1

• Claus-Peter Schnorr:
  Refined Analysis and Improvements on Some Factoring Algorithms. 1-15
  
• Joos Heintz, Malte Sieveking:
  Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables. 16-28
  
• Franco P. Preparata, Jean Vuillemin:
  Area-Time Optimal VLSI Networks for Computing Integer Multiplications and Discrete Fourier Transform. 29-40
  

Session 2

• Jia-Wei Hong, Kurt Mehlhorn, Arnold L. Rosenberg:
  Cost Tradeoffs in Graph Embeddings, with Applications (Preliminary Version). 41-55
  
• John H. Reif:
  Minimum S-T Cut of a Planar Undirected Network in O(n log²(n)) Time. 56-67
  
• Emo Welzl:
  On the Density of Color-Families. 68-72
  

Session 3

• Catriel Beeri, Moshe Y. Vardi:
  The Implication Problem for Data Dependencies. 73-85
  
• Johann A. Makowsky:
  Characterizing Data Base Dependencies. 86-97
  
• Micha Sharir:
  Data Flow Analysis of Applicative Programs. 98-113
  

Session 4

• Neil D. Jones:
  Flow Analysis of Lambda Expressions (Preliminary Version). 114-128
  
• Jacques Loeckx:
  Algorithmic Specifications of Abstract Data Types. 129-147
  
• P. A. Subrahmanyam:
  Nondeterminism in Abstract Data Types. 148-164
  

Session 5

• Jeffrey D. Ullman:
  A View of Directions in Relational Database Theory. 165-176
  
• Christophe Reutenauer:
  A New Characterization of the Regular Languages. 177-183
  

Session 6

• Jean-Eric Pin:
  Languages reconnaissables et codage prefixe pur. 184-192
  
• Joost Engelfriet, Gilberto Filé:
  Passes, Sweeps and Visits. 193-207
  

Session 7

• Seppo Sippu, Eljas Soisalon-Soininen:
  On LALR(1) Testing. 208-217
  
• Esko Ukkonen:
  On Size Bounds for Deterministic Parsers. 218-228
  
• Yair Itzhaik, Amiram Yehudai:
  A Decision Procedure for the Equivalence of Two DPDAs, One of Which is Linear (Extended Abstract). 229-237
  

Session 8

• Albert R. Meyer, Robert S. Streett, Grazyna Mirkowska:
  The Deducibility Problem in Propositional Dynamic Logic. 238-248
  
• Mordechai Ben-Ari, Joseph Y. Halpern, Amir Pnueli:
  Finite Models for Deterministic Propositional Dynamic Logic. 249-263
  
• Daniel J. Lehmann, Amir Pnueli, Jonathan Stavi:
  Impartiality, Justice and Fairness: The Ethics of Concurrent Termination. 264-277
  

Session 9

• Aviezri S. Fraenkel, David Lichtenstein:
  Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N. 278-293
  
• Oscar H. Ibarra, Brian S. Leininger, Shlomo Moran:
  On the Complexity of Simple Arithmetic Expressions. 294-304
  
• Marc Snir:
  Proving Lower Bounds for Linar Decision Trees. 305-315
  

Session 10

• Meera Blattner, Michel Latteux:
  Parikh-Bounded Languages. 316-323
  
• Juhani Karhumäki:
  Generalized Parikh Mappings and Homomorphisms. 324-332
  
• Sorin Istrail:
  Chomsky-Schützenberger Representations for Families of Languages and Grammatical Types. 333-347
  

Session 11

• Jan A. Bergstra, J. V. Tucker:
  Algebraically Specified Programming Systems and Hoare's Logic. 348-362
  

Session 12

• Mark Moriconi, Richard L. Schwartz:
  Automatic Construction of Verification Condition Generators From Hoare Logics. 363-377
  
• Ravi Sethi:
  Circular Expressions: Elimination of Static Environments. 378-392
  

Session 13

• Bruno Courcelle:
  An Axiomatic Approach to the Korenjak-Hopcroft Algorithms. 393-407
  
• Andrzej Ehrenfeucht, Grzegorz Rozenberg:
  On the (Generalized) Post Correspondence Problem with Lists of Length 2. 408-416
  
• Alon Itai, Alan G. Konheim, Michael Rodeh:
  A Sparse Table Implementation of Priority Queues. 417-431
  

Session 14

• Alberto Pettorossi:
  Comparing and Putting Together Recursive Path Ordering, Simplification Orderings and Non-Ascending Property for Termination Proofs of Term Rewriting Systems. 432-447
  
• Nachum Dershowitz:
  Termination of Linear Rewriting Systems (Preliminary Version). 448-458
  
• Amir Pnueli, R. Zarhi:
  Realizing an Equational Specification. 459-478
  

Session 15

• Krzysztof R. Apt, Gordon D. Plotkin:
  A Cook's Tour of Countable Nondeterminism. 479-494
  
• Eitan M. Gurari, Oscar H. Ibarra:
  The Complexity of Decision Problems for Finite-Turn Multicounter Machines. 495-505
  
• K. N. King:
  Alternating Multihead Finite Automata (Extended Abstract). 506-520
  

Session 16

• Judea Pearl:
  The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm. 521-529
  
• Karl J. Lieberherr:
  Uniform Complexity and Digital Signatures. 530-543
  
• Adi Shamir:
  On the Generation of Cryptographically Strong Pseudo-Random Sequences. 544-550
  

Errata

• Johann A. Makowsky:
  Errata: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory. 551
  , ->ICALP 1980: 409-421