17. ICALP 1990: Warwick University, England

Session 1

• Stefan Näher, Kurt Mehlhorn:
  LEDA: A Library of Efficient Data Types and Algorithms. 1-5
  
• Martin Dietzfelbinger, Friedhelm Meyer auf der Heide:
  A New Universal Class of Hash Functions and Dynamic Hashing in Real Time. 6-19
  

Session 2

• Jon G. Riecke:
  A Complete and Decidable Proof System for Call-by-Value Equalities (Preliminary Report). 20-31
  
• Michael I. Schwartzbach:
  Static Correctness of Hierarchical Procedures. 32-45
  
• Sophie Malecki:
  Generic Terms Having No Polymorphic Types. 46-59
  

Session 3

• Daniel Krob:
  A Complete System of B-Rational Identities. 60-73
  
• Aldo de Luca, Stefano Varricchio:
  On Non-Counting Regular Classes. 74-87
  
• Marcella Anselmo:
  Two-Way Automata with Multiplicity. 88-102
  
• Werner Kuich:
  Omega-Continuous Semirings, Algebraich Systems and Pushdown Automata. 103-110
  

Session 4

• Viliam Geffert: Nondeterministic Computations in Sublogarithmic Space and Space Constructibility. 111-124 , journal version: SIAM J. Comput. 20(3): 484-498(1991)
• Juraj Wiedermann:
  Normalizing and Accelerating RAM Computations and the Problem of Reasonable Space Measures. 125-138
  
• Osamu Watanabe:
  A Formal Study of Learning via Queries. 139-152
  
• Sanjay Jain, Arun Sharma:
  Language Learning by a "Team" (Extended Abstract). 153-166
  

Session 5

• Robin Milner:
  Functions as Processes. 167-180
  
• Radha Jagadeesan, Prakash Panangaden:
  A Domain-Theoretic Model for a Higher-Order Process Calculus. 181-194
  
• Manfred Droste:
  Concurrency, Automata and Domains. 195-208
  

Session 6

• Matthew Hennessy, Anna Ingólfsdóttir:
  A Theory of Communicating Processes with Value-Passing. 209-219
  
• Philippe Flajolet, Paolo Sipala, Jean-Marc Steyaert:
  Analytic Variations on the Common Subexpression Problem. 220-234
  
• Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn:
  Can A Maximum Flow be Computed on o(nm) Time? 235-248
  

Session 7

• Alexander A. Razborov:
  On the Distributional Complexity of Disjontness. 249-253
  
• Evangelos Kranakis, Danny Krizanc, Jacob van den Berg:
  Computing Boolean Functions on Anonymous Networks. 254-267
  
• Oded Goldreich, Hugo Krawczyk:
  On the Composition of Zero-Knowledge Proof Systems. 268-282
  
• Ronald V. Book, Jack H. Lutz, Shouwen Tang:
  Additional Queries to Random and Pseudorandom Oracles. 283-293
  

Session 8

• Alexander Moshe Rabinovich, Boris A. Trakhtenbrot:
  Communication among Relations (Extended Abstract). 294-307
  
• Prakash Panangaden, Vasant Shanbhogue, Eugene W. Stark:
  Stability and Sequentiality in Dataflow Networks. 308-321
  
• Rajeev Alur, David L. Dill:
  Automata For Modeling Real-Time Systems. 322-335
  
• Costas Courcoubetis, Mihalis Yannakakis:
  Markov Decision Processes and Regular Events (Extended Abstract). 336-349
  

Session 9

• Jan Willem Klop:
  Term Rewriting Systems: From Church-Rosser to Knuth-Bendix and Beyond. 350-369
  
• Rakesh M. Verma, I. V. Ramakrishnan:
  Nonoblivious Normalization Algorithms for Nonlinear Rewrite Systems. 370-385
  
• Catuscia Palamidessi:
  Algebraic Properties of Idempotent Substitutions. 386-399
  

Session 10

• David P. Dobkin, David G. Kirkpatrick:
  Determining the Separation of Preprocessed Polyhedra - A Unified Approach. 400-413
  
• Leonidas J. Guibas, Donald E. Knuth, Micha Sharir:
  Randomized Incremental Construction of Delaunay and Voronoi Diagrams. 414-431
  
• Richard Cole, Michael T. Goodrich, Colm Ó'Dúnlaing:
  Merging Free Trees in Parallel for Efficient Voronoi Diagram Construction (Preliminary Version). 432-445
  

Session 11

• David S. Johnson:
  Local Optimization and the Traveling Salesman Problem. 446-461
  
• Mark Jerrum, Alistair Sinclair:
  Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). 462-475
  
• John E. Savage, Markus G. Wloka:
  On Parallelizing Graph-Partitioning Heuristics. 476-489
  

Session 12

• Christian Choffrut:
  Iterated Substitutions and Locally Catanative Systems: A Decidability Result in the Binary Case. 490-500
  
• Mireille Clerbout, Michel Latteux, Yves Roos:
  Decomposition of Partial Commutations. 501-511
  
• Maryse Pelletier:
  Boolean Closure and Unambiguity of Rational Sets. 512-525
  

Session 13

• Kim Guldstrand Larsen, Liu Xinxin:
  Compositionality Through an Operational Semantics of Contexts. 526-539
  
• Joachim Parrow:
  Structural and Behavioural Equivalences of Networks. 540-552
  
• Doron Peled, Amir Pnueli:
  Proving Partial Order Liveness Properties. 553-571
  
• Frank S. de Boer:
  A Proof System for the Parallel Object-Oriented Language POOL. 572-585
  

Session 14

• Norbert Blum:
  A New Approach to Maximum Matching in General Graphs. 586-597
  
• Giuseppe Di Battista, Roberto Tamassia:
  On-Line Graph Algorithms with SPQR-Trees. 598-611
  
• Victor Y. Pan, John H. Reif:
  On the Bit-Complexity of Discrete Solutions of PDEs: Compact Multigrid. 612-625
  
• Jan Friso Groote, Frits W. Vaandrager:
  An Efficient Algorithm for Branching Bisimulation and Stuttering Equivalence. 626-638
  

Session 15

• Neil D. Jones:
  Partial Evaluation, Self-Application and Types. 639-659
  
• J. V. Tucker, S. S. Wainer, Jeffery I. Zucker:
  Provable Computable Functions on Abstract Data Types. 660-673
  
• Hubert Comon:
  Equational Formulas in Order-Sorted Algebras. 674-688
  

Session 16

• Michael T. Goodrich, Mikhail J. Atallah, Mark H. Overmars:
  An Input-Size/Output-Size Trade-Off in the Time-Complexity of Rectilinear Hidden Surface Removal (Preliminary Version). 689-702
  
• Helmut Alt, Johannes Blömer, Hubert Wagener:
  Approximation of Convex Polygons. 703-716
  
• Frank Hoffmann:
  On the Rectilinear Art Gallery Problem (Extended Abstract). 717-728
  

Session 17

• Yossi Matias, Uzi Vishkin:
  On Parallel Hashing and Integer Sorting (Extended Summary). 729-743
  
• Prabhakar Radge:
  The Parallel Simplicity of Compaction and Chaining. 744-751
  
• Faron Moller:
  The Importance of the Left Merge Operator in Process Algebras. 752-764
  
• Sanjiva Prasad, Alessandro Giacalone, Prateek Mishra:
  Operational and Algebraic Semantics for Facile: A Symmetric Integration of Concurrent and Functional Programming. 765-778