[Prev][Next][Index][Thread]

ICALP '98: List of Accepted Papers

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
-------------------------------------------------------------------------------