The papers listed below were accepted for ICALP '98, which will be held on July 13-17 in Aalborg, Denmark. Further information on ICALP '98 is available on the Web at http://www.cs.auc.dk/icalp98/ ------------------------------------------------------------------------------- A duality between Kruskal and Dershowitz theorems by Paul-Andre Mellies ------------------------------------------------------------------------------- A genuinely polynomial-time algorithms for sampling two-rowed contingency tables by Martin Dyer, Catherine Greenhill ------------------------------------------------------------------------------- Efficient Simulations by Queue Machines by Holger Petersen, John Michael Robson ------------------------------------------------------------------------------- On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology by Tatsuya Akutsu, Mutsunori Yagiura ------------------------------------------------------------------------------- Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees by David Peleg ------------------------------------------------------------------------------- Deterministic Polylog Approximation for Minimum Communication Spanning Trees by David Peleg, Eilon Reshef ------------------------------------------------------------------------------- A Good Class of Tree Automata and Application to Inductive Theorem Proving by Denis Lugiez ------------------------------------------------------------------------------- On Computing the Entropy of Cellular Automata by Michele D'amico, Giovanni Manzini, Luciano Margara ------------------------------------------------------------------------------- On Branching Programs With Bounded Uncertainty by Stasys Jukna, Stanislav Zak ------------------------------------------------------------------------------- CONS-Free Programs with Tree Input by Amir Ben-Amram, Holger Petersen ------------------------------------------------------------------------------- Global/Local Subtyping and Capability Inference for a Distributed pi-calculus by Peter Sewell ------------------------------------------------------------------------------- Computing Mimicking Networks by Shiva Chaudhuri, K.V. Subrahmanyam, Frank Wagner, Christos Zaroliagis ------------------------------------------------------------------------------- Robust asynchronous protocols are finite-state by Madhavan Mukund, K Narayan Kumar, Jaikumar Radhakrishnan, Milind Sohoni ------------------------------------------------------------------------------- Optimal Sampling Strategies in Quicksort by Conrado Martinez, Salvador Roura ------------------------------------------------------------------------------- The relevance of proof-irrelevance by Gilles Barthe ------------------------------------------------------------------------------- Deciding global partial-order properties by Rajeev Alur, Ken McMillan, Doron Peled ------------------------------------------------------------------------------- Efficient Minimization of Numerical Summation Errors by Ming-Yang Kao, Jie Wang ------------------------------------------------------------------------------- Simpler and Faster Static AC^0 Dictionaries by Torben Hagerup ------------------------------------------------------------------------------- Structural Recursive Definitions in Type Theory by Eduardo Gimenez ------------------------------------------------------------------------------- On the Determinization of Weighted Finite Automata by Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook ------------------------------------------------------------------------------- A Degree-Decreasing Lemma for (MOD q -- MOD p) Circuits by Vince Grolmusz ------------------------------------------------------------------------------- Improved Pseudorandom Generators for Combinatorial Rectangles by Chi-Jen Lu ------------------------------------------------------------------------------- Checking Strong/Weak Bisimulation Equivalences and Observation by Zhoujun Li, Huowang Chen ------------------------------------------------------------------------------- On Existentially First-Order Definable Languages and their Relation to NP by Bernd Borchert, Dietrich Kuske, Frank Stephan ------------------------------------------------------------------------------- Morphing simple polygons optimally - a proof for an improved conjecture by T. Graf, V. Kamakoti ------------------------------------------------------------------------------- Metric Semantics for True Concurrent Real Time by Christel Baier, Joost-Pieter Katoen, Diego Latella ------------------------------------------------------------------------------- Static and Dynamic Low-Congested Interval Routing Schemes by Serafino Cicerone, Gabriele Di Stefano, Michele Flammini ------------------------------------------------------------------------------- Independent sets with domination constraint by Magnus M. Halldorsson, Jan Kratochvil, Jan Arne Telle ------------------------------------------------------------------------------- Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP by Ivan Damgaard, Birgit Pfitzmann ------------------------------------------------------------------------------- A modular approach to denotational semantics by John Power, Giuseppe Rosolini ------------------------------------------------------------------------------- Generalised Flowcharts and Games by Pasquale Malacaria, Chris Hankin ------------------------------------------------------------------------------- Efficient approximation algorithms for the {sc Subset-Sums Equality} problem by Cristina Bazgan, Miklos Santha, Zsolt Tuza ------------------------------------------------------------------------------- A complex eample of a simplifying rewrite system by H. Touzet ------------------------------------------------------------------------------- Low-Bandwidth Routing and Electrical Power Networks by Doug Cook, Vance Faber, Madhav Marathe, Aravind Srinivasan, Yoram J. Sussmann ------------------------------------------------------------------------------- Deciding Bisimulation-Like Equivalences with Finite-State Processes by Petr Jancar, Antonin Kucera, Richard Mayr ------------------------------------------------------------------------------- The equivalence problem for propositional programs is decidable in polynomial time. by Vladimir A. Zakharov ------------------------------------------------------------------------------- A Total AC-Compatible Reduction Ordering on Higher-Order Terms by Daria Walukiewicz ------------------------------------------------------------------------------- Partial-Congruence Factorization of Bisimilarity Induced by Open Maps by Slawomir Lasota ------------------------------------------------------------------------------- The Regular Real-Time Languages by Henzinger Tom, Raskin Jean-Francois, Schobbens Pierre-Yves ------------------------------------------------------------------------------- Multi-Stage Programming: Axiomatization and Type Safety by Walid Taha, Zine-El-Abidine Benaissa, Tim Sheard ------------------------------------------------------------------------------- Limited Wavelength Conversion in All-Optical Tree Networks by Luisa Gargano ------------------------------------------------------------------------------- Difficult configurations - on the complexity of LTrL by Igor Walukiewicz ------------------------------------------------------------------------------- Inversion of Circulant Matrices over Z_m by dario bini, gianna del corso, giovanni manzini, luciano margara ------------------------------------------------------------------------------- A Hierarchy of Equivalences for Asynchronous Calculi by Cedric Fournet, Georges Gonthier ------------------------------------------------------------------------------- Explicit Substitutions for Constructive Necessity by Neil Ghani, Valeria de Paiva, Eike Ritter ------------------------------------------------------------------------------- Locally Periodic Infinite Words and a Chaotic Behaviour by Juhani Karhumäki, Arto Lepistö, Wojciech Plandowski ------------------------------------------------------------------------------- BRIDGES FOR CONCATENATION HIERARCHIES by Jean-Eric Pin ------------------------------------------------------------------------------- Application of lempel-ziv encodings to the solution of words equations by Wojciech Plandowski, Wojciech Rytter ------------------------------------------------------------------------------- Constraint Automata and the Complexity of Recursive Subtype Entailment by Fritz Henglein, Jakob Rehof ------------------------------------------------------------------------------- Randomness Spaces by Peter Hertling, Klaus Weihrauch ------------------------------------------------------------------------------- Power of cooperation and multihead finite systems. by Pavol Duri\v{s}, Tomasz Jurdzinski, Miroslaw Kutylowski, Krzysztof Lorys ------------------------------------------------------------------------------- A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity by Artur Czumaj, Andrzej Lingas ------------------------------------------------------------------------------- Bulk-synchronous parallel multiplication of Boolean matrices by Alexandre Tiskin ------------------------------------------------------------------------------- Reasoning about The Past with Two-Way Automata by Moshe Y. Vardi ------------------------------------------------------------------------------- Translation Validation for Synchronous Languages by A. Pnueli, O. Shtrichman, M. Siegel ------------------------------------------------------------------------------- Quantum Counting by Gilles Brassard, Peter Hoyer, Alain Tapp ------------------------------------------------------------------------------- Complete Proof Systems for Observation Congruences in Finite-Control pi-Calculus by Huimin Lin ------------------------------------------------------------------------------- On asynchrony in name-passing calculi by Massimo Merro, Davide Sangiorgi ------------------------------------------------------------------------------- A Simple Solution to Type Specialization by Olivier Danvy ------------------------------------------------------------------------------- Concatenable Graph Processes: Relating Processes and Derivation Traces by Paolo Baldan, Andrea Corradini, Ugo Montanari ------------------------------------------------------------------------------- On the Expressiveness of Real and Integer Arithmetic Automata by Bernard Boigelot, Stephane Rassart, Pierre Wolper ------------------------------------------------------------------------------- Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method by Thore Husfeldt, Theis Rauhe ------------------------------------------------------------------------------- Reset nets between decidability and undecidability by C. Dufourd, A. Finkel, Ph. Schnoebelen ------------------------------------------------------------------------------- Totality, definability and boolean ciruits by Antonio Bucciarelli, Ivano Salvo ------------------------------------------------------------------------------- Concurrent Constraints in the Fusion Calculus by Björn Victor, Joachim Parrow ------------------------------------------------------------------------------- Simple Linear-Time Algorithms for Minimal Fixed Points by Xinxin Liu, Scott A. Smolka ------------------------------------------------------------------------------- Axioms for Contextual Net Processes by Fabio Gadducci, Ugo Montanari ------------------------------------------------------------------------------- An algebraic approach to communication complexity by Jean-Francois Raymond, Pascal Tesson, Denis Therien ------------------------------------------------------------------------------- Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses by R. C-N. Chuang, A. Garg, X. He, M-Y. Kao, H-I. Lu ------------------------------------------------------------------------------- Non-Interactive Statistical Zero-Knowledge: a Complete Problem and Closure Properties by Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung -------------------------------------------------------------------------------