25. ICALP 1998: Aalborg, Denmark

Invited Lecture

• Yonit Kesten, Amir Pnueli, Li-on Raviv:
  Algorithmic Verification of Linear Temporal Logic Specifications. 1-16
  

Complexity

• Bernd Borchert, Dietrich Kuske, Frank Stephan:
  On Existentially First-Order Definable Languages and Their Relation to NP. 17-28
  
• Jean-François Raymond, Pascal Tesson, Denis Thérien:
  An Algebraic Approach to Communication Complexity. 29-40
  

Verification

• Rajeev Alur, Kenneth L. McMillan, Doron Peled:
  Deciding Global Partial-Order Properties. 41-52
  
• Xinxin Liu, Scott A. Smolka:
  Simple Linear-Time Algorithms for Minimal Fixed Points (Extended Abstract). 53-66
  

Data Structures

• Thore Husfeldt, Theis Rauhe:
  Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method. 67-78
  
• Torben Hagerup:
  Simpler and Faster Dictionaries on the AC⁰ RAM. 79-90
  

Concurrency

• Slawomir Lasota:
  Partial-Congruence Factorization of Bisimilarity Induced by Open Maps. 91-102
  
• Catherine Dufourd, Alain Finkel, Ph. Schnoebelen:
  Reset Nets Between Decidability and Undecidability. 103-115
  

Invited Lecture

• Mark H. Overmars:
  Geometric Algorithms for Robotic Manipulation. 116-117
  

Computational Geormetry

• Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, Hsueh-I Lu:
  Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses. 118-129
  
• Thorsten Graf, Kamakoti Veezhinathan:
  Reducing Simple Polygons to Triangles - A Proof for an Improved Conjecture. 130-139
  

Automata and Temporal Logic

• Igor Walukiewicz:
  Difficult Configurations - On the Complexity of LTrL. 140-151
  
• Bernard Boigelot, Stéphane Rassart, Pierre Wolper:
  On the Expressiveness of Real and Integer Arithmetic Automata (Extended Abstract). 152-163
  

Algorithms

• David Peleg:
  Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees. 164-175
  
• Magnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle:
  Independent Sets with Domination Constraints. 176-187
  

Infinite State Systems

• Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni:
  Robust Asynchronous Protocols Are Finite-State. 188-199
  
• Petr Jancar, Antonín Kucera, Richard Mayr:
  Deciding Bisimulation-Like Equivalences with Finite-State Processes. 200-211
  

Invited Lecture

• Avi Wigderson:
  Do Probabilistic Algorithms Outperform Deterministic Ones? 212-214
  

Complexity

• Vince Grolmusz:
  A Degree-Decreasing Lemma for (MOD q - MOD p) Circuits. 215-222
  
• Chi-Jen Lu:
  Improved Pseudorandom Generators for Combinatorial Rectangles. 223-234
  

Verification

• Amir Pnueli, Ofer Strichman, Michael Siegel:
  Translation Validation for Synchronous Languages. 235-246
  
• Vladimir A. Zakharov:
  An Efficient and Unified Approach to the Decidability of Equivalence of Propositional Programs. 247-258
  

Complexity

• Stasys Jukna, Stanislav Zák:
  On Branching Programs With Bounded Uncertainty (Extended Abstract). 259-270
  
• Amir M. Ben-Amram, Holger Petersen:
  CONS-Free Programs with Tree Input (Extended Abstract). 271-282
  

Concurrency

• Paolo Baldan, Andrea Corradini, Ugo Montanari:
  Concatenable Graph Processes: Relating Processes and Derivation Traces. 283-295
  
• Fabio Gadducci, Ugo Montanari:
  Axioms for Contextual Net Processes. 296-308
  

Invited Lecture

• Andrew M. Pitts:
  Existential Types: Logical Relations and Operational Equivalence. 309-326
  

Algorithms

• Conrado Martínez, Salvador Roura:
  Optimal Sampling Strategies in Quicksort. 327-338
  
• Martin E. Dyer, Catherine S. Greenhill:
  A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables. 339-350
  

Semantics

• John Power, Giuseppe Rosolini:
  A Modular Approach to Denotational Semantics. 351-362
  
• Pasquale Malacaria, Chris Hankin:
  Generalised Flowcharts and Games. 363-374
  

Approximation

• Ming-Yang Kao, Jie Wang:
  Efficient Minimization of Numerical Summation Errors. 375-386
  
• Cristina Bazgan, Miklos Santha, Zsolt Tuza:
  Efficient Approximation Algorithms for the Subset-Sums Equality Problem. 387-396
  

Theorem Proving

• Eduardo Giménez:
  Structural Recursive Definitions in Type Theory. 397-408
  
• Denis Lugiez:
  A Good Class of Tree Automata and Application to Inductive Theorem Proving. 409-420
  

Formal Languages

• Juhani Karhumäki, Arto Lepistö, Wojciech Plandowski:
  Locally Periodic Infinite Words and a Chaotic Behaviour. 421-430
  
• Jean-Eric Pin:
  Bridges for Concatenation Hierarchies. 431-442
  

Pi-calculus

• Huimin Lin:
  Complete Proof Systems for Observation Congruences in Finite-Control pi-Calculus. 443-454
  
• Björn Victor, Joachim Parrow:
  Concurrent Constraints in the Fusion Calculus. 455-469
  

Automata and BSP

• Michele D'amico, Giovanni Manzini, Luciano Margara:
  On Computing the Entropy of Cellular Automata. 470-481
  
• Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery Westbrook:
  On the Determinization of Weighted Finite Automata. 482-493
  
• Alexandre Tiskin:
  Bulk-Synchronous Parallel Multiplication of Boolean Matrices. 494-506
  

Rewriting

• Hélène Touzet:
  A Complex Example of a Simplifying Rewrite System. 507-517
  
• Paul-André Melliès:
  On a Duality Between Kruskal and Dershowitz Theorems. 518-529
  
• Daria Walukiewicz:
  A Total AC-Compatible Reduction Ordering on Higher-Order Terms. 530-542
  

Invited Lecture

• Thomas A. Henzinger:
  Model Checking Game Properties of Multi-agent Systems (Abstract). 543
  

Networks and Routing

• Luisa Gargano:
  Limited Wavelength Conversion in All-Optical Tree Networks. 544-555
  
• Shiva Chaudhuri, K. V. Subrahmanyam, Frank Wagner, Christos D. Zaroliagis:
  Computing Mimicking Networks. 556-567
  

Real Time

• Christel Baier, Joost-Pieter Katoen, Diego Latella:
  Metric Semantics for True Concurrent Real Time. 568-579
  
• Thomas A. Henzinger, Jean-François Raskin, Pierre-Yves Schobbens:
  The Regular Real-Time Languages. 580-591
  

Networks and Routing

• Serafino Cicerone, Gabriele Di Stefano, Michele Flammini:
  Static and Dynamic Low-Congested Interval Routing Schemes. 592-603
  
• Doug Cook, Vance Faber, Madhav V. Marathe, Aravind Srinivasan, Yoram J. Sussmann:
  Low-Bandwidth Routing and Electrical Power Networks. 604-615
  

Automata and Temporal Logic

• Fritz Henglein, Jakob Rehof:
  Constraint Automata and the Complexity of Recursive Subtype Entailment. 616-627
  
• Moshe Y. Vardi:
  Reasoning about The Past with Two-Way Automata. 628-641
  

Invited Lecture

• Leslie G. Valiant:
  A Neuroidal Architecture for Cognitive Computation. 642-669
  

Approximation

• David Peleg, Eilon Reshef:
  Deterministic Polylog Approximation for Minimum Communication Spanning Trees. 670-681
  
• Artur Czumaj, Andrzej Lingas:
  A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity. 682-694
  

Pi-calculus

• Peter Sewell:
  Global/Local Subtyping and Capability Inference for a Distributed pi-calculus. 695-706
  
• Zhoujun Li, Huowang Chen:
  Checking Strong/Weak Bisimulation Equivalences and Observation Congruence for the pi-Calculus. 707-718
  

Algorithms

• Dario Bini, Gianna M. Del Corso, Giovanni Manzini, Luciano Margara:
  Inversion of Circulant Matrices over Z_m. 719-730
  
• Wojciech Plandowski, Wojciech Rytter:
  Application of Lempel-Ziv Encodings to the Solution of Words Equations. 731-742
  

Theorem Proving

• Neil Ghani, Valeria de Paiva, Eike Ritter:
  Explicit Substitutions for Constructive Necessity. 743-754
  
• Gilles Barthe:
  The Relevance of Proof-Irrelevance. 755-768
  

Invited Lecture

• Gilles Brassard:
  New Horizons in Quantum Information Processing. 769-771
  

Zero-Knowledge

• Ivan Damgård, Birgit Pfitzmann:
  Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP. 772-783
  
• Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung:
  Image Density is Complete for Non-Interactive-SZK (Extended Abstract). 784-795
  

Semantics

• Peter Hertling, Klaus Weihrauch:
  Randomness Spaces. 796-807
  
• Antonio Bucciarelli, Ivano Salvo:
  Totality, Definability and Boolean Ciruits. 808-819
  

Quantum Computing and Computational Biology

• Gilles Brassard, Peter Høyer, Alain Tapp:
  Quantum Counting. 820-831
  
• Tatsuya Akutsu, Mutsunori Yagiura:
  On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology. 832-843
  

Pi-calculus

• Cédric Fournet, Georges Gonthier:
  A Hierarchy of Equivalences for Asynchronous Calculi. 844-855
  
• Massimo Merro, Davide Sangiorgi:
  On Asynchrony in Name-Passing Calculi. 856-867
  

Invited Lecture

• Martín Abadi:
  Protection in Programming-Language Translations. 868-883
  

Automata

• Holger Petersen, John Michael Robson:
  Efficient Simulations by Queue Machines. 884-895
  
• Pavol Duris, Tomasz Jurdzinski, Miroslaw Kutylowski, Krzysztof Lorys:
  Power of Cooperation and Multihead Finite Systems. 896-907
  

Programming Languages and Types

• Olivier Danvy:
  A Simple Solution to Type Specialization. 908-917
  
• Walid Taha, Zine-El-Abidine Benaissa, Tim Sheard:
  Multi-Stage Programming: Axiomatization and Type Safety. 918-929