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. Springer 1981 Lecture Notes in Computer Science ISBN 3-540-10843-2
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
- 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
Session 7
- 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
- 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
Session 15
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T214307 by the dblp team