8. ICALP 1981: Acre (Akko), Israel

Shimon Even, Oded Kariv (Eds.): Automata, Languages and Programming, 8th Colloquium, Acre (Akko), Israel, July 13-17, 1981, Proceedings. Lecture Notes in Computer Science 115 Springer 1981, ISBN 3-540-10843-2 BibTeX

@proceedings{DBLP:conf/icalp/1981,
  editor    = {Shimon Even and
               Oded Kariv},
  title     = {Automata, Languages and Programming, 8th Colloquium, Acre (Akko),
               Israel, July 13-17, 1981, Proceedings},
  booktitle = {ICALP},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {115},
  year      = {1981},
  isbn      = {3-540-10843-2},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Session 1

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

Session 2

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

Session 3

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

Session 4

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

Session 5

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

Session 6

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

Session 7

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

Session 8

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

Session 9

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

Session 10

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

Session 11

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

Session 12

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

Session 13

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

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 BibTeX
Nachum Dershowitz: Termination of Linear Rewriting Systems (Preliminary Version). 448-458 BibTeX
Amir Pnueli, R. Zarhi: Realizing an Equational Specification. 459-478 BibTeX

Session 15

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

Session 16

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

Errata

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