Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 List of Accepted Papers - ICALP' 2000
ICALP' 2000
27th International Colloquium on
Automata, Languages and Programming
July 9-15, 2000, Geneva, Switzerland
LIST OF ACCEPTED PAPERS
without any ordering
Improved algorithms for finding level ancestors in dynamic trees
Stephen Alstrup, Jacob Holm
Determinization of transducers over infinite words
Marie-Pierre Béal, Olivier Carton
Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
Beate Bollig, Ingo Wegener
Lower bounds are not easier over the reals: inside PH
Hervé Fournier, Pascal Koiran
Resource augmentation for online bounded space bin packing
János Csirik, Gerhard J. Woeginger
The global power of additional queries to p-random oracles
Wolfgang Merkle
A bound on the capacity of backoff and acknowledgement-based protocols
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson
Deterministic algorithms for k-SAT based on covering codes and local search
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning
An optimal online algorithm for bounded space variable-sized bin packing
Steven S. Seiden
Average bit-complexity of euclidean algorithms
Ali Akhavi, Brigitte Vallée
Clique is hard to approximate within n^(1-o(1))
Lars Engebretsen, Jonas Holmerin
Strong inapproximability of the basic k-Spanner Problem
Michael Elkin, David Peleg
Extended notions of security for multicast public key cryptosystems
Olivier Baudron, David Pointcheval, Jacques Stern
Testing acyclicity of directed graphs in sublinear time
Michael Bender, Dana Ron
Monotone proofs of the pigeon hole principle
Albert Atserias, Nicola Galesi, Ricard Gavalda
Tight size bounds for packet headers in narrow meshes
Micah Adler, Faith Fich, Leslie Ann Goldberg, Mike Paterson
Unlearning helps
Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan
Planar maps and Airy phenomena
Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michèle Soria
Homogenization and the polynomial calculus
Josh Buresh-Oppenheim, Matt Clegg, Russell Impagliazzo, Toniann Pitassi
Approximating the independence number and the chromatic number in expected polynomial time
Michael Krivelevich, Van Vu
Closest vectors, successive minima, and dual HKZ-bases of lattices
Johannes Blömer
Hardness of set cover with intersection 1
V.S. Anil Kumar, Sunil Arya, H. Ramesh
Optimal projective algorithms for the list update problem
Christoph Ambühl, Bernd Gärtner, Bernhard von Stengel
Fast approximation schemes for euclidean multi-connectivity problems
Artur Czumaj, Andrzej Lingas
An optimal minimum spanning tree algorithm
Seth Pettie, Vijaya Ramachandran
Deterministic radio broadcasting
Bogdan S. Chlebus, Leszek Gasieniec, Anna Östlin, John Michael Robson
Approximating minimum spanning sets in hypergraphs and polymatroids
Gregor Baudis, Clemens Gröpl, Stefan Hougardy, Till Nierhoff, Hans Jürgen Prömel
Improved shortest paths on the word RAM
Torben Hagerup
On the power of tree-walking automata
Frank Neven, Thomas Schwentick
One-round secure computation and secure autonomous mobile agents
Christian Cachin, Jan Camenisch, Joe Kilian, Joy Müller
Measures of nondeterminism in finite automata
Juraj Hromkoviç, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert
The many faces of a translation
Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer
Scalable secure storage when half the system is faulty
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
Round-optimal and abuse-free multi-party contract signing
Birgit Baum-Waidner, Michael Waidner
Dual-bounded hypergraphs: Generating partial and multiple transversals
Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino
On the centralizer of a finite set
Juhani Karhumäki, Ion Petre
Computing the girth of a planar graph
Hristo N. Djidjev
Approximate TSP in graphs with forbidden minors
Michelangelo Grigni
Polynomial time approximation schemes for general multiprocessor job shop scheduling
Klaus Jansen, Lorant Porkolab
Necessary and sufficient assumptions for non-interactive zero-knowledge proofs of knowledge for all NP relations
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano
Computational PCP: Short one-round proofs for NP
W. Aiello, S. Bhatt, R. Ostrovsky, S. Rajagopalan
Gales and the constructive dimension of individual sequences
Jack Lutz
Wavelength assignment problem on all-optical networks with k fibres per link
Luciano Margara, Janos Simon
On the Complexity of Bisimulation Problems for Basic Parallel Processes
Richard Mayr
An automata-theoretic completeness proof for Interval Temporal Logic
B. C. Moszkowski
LTL is expressively complete for Mazurkiewicz traces
Volker Diekert, Paul Gastin
On the logical characterisation of performability properties
Christel Baier, Boudewijn Haverkort, Holger Hermanns, Joost-Pieter Katoen
Efficient Verification Algorithms for One-Counter Processes
Antonin Kucera
Reasoning about message passing in finite state environments
B. Meenakshi, R. Ramanujam
Closed Types as a Simple Approach to Safe Imperative Multi-Stage Programming
Cristiano Calcagno, Eugenio Moggi, Walid Taha
Lax Logical Relations
Gordon Plotkin, John Power, Donald Sannella, Robert Tennent
Fully-abstract Statecharts Semantics via Intuitionistic Kripke Structures
Gerald Luettgen, Michael Mendler
On deciding if deterministic Rabin language is in Buchi class
Tomasz Fryderyk Urbanski
Decidable first-order transition logics for PA-processes
D. Lugiez, Ph. Schnoebelen
Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System
Barbara Koenig
A Statically Allocated Parallel Functional Language
Alan Mycroft, Richard Sharp
Variable Independence, Quantifier Elimination, and Constraint Representations
Leonid Libkin
Algebraic Models for Contextual Nets
Roberto Bruni, Vladimiro Sassone
On Message Sequence Graphs and Finitely Generated Regular MSC Languages
Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P.S. Thiagarajan
The measurement process in domain theory
Keye Martin
On the Representation of Timed Polyhedra
Olivier Bournez, Oded Maler
Reasoning about Idealized Algol Using Regular Languages
Dan R. Ghica, Guy McCusker
Information Flow vs. Resource Access in the Asynchronous Pi-Calculus
Matthew Hennessy, James Riely
Revisiting the correspondence between cut elimination and normalisation
Jose Espirito Santo
A Finite $\omega$-complete Equational Specification of Interleaving
Wan Fokkink, Bas Luttik
A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors
Mario Bravetti, Roberto Gorrieri
A New Unfolding Approach to LTL Model Checking
Javier Esparza, Keijo Heljanko
Infinite series-parallel posets: logic and languages
Dietrich Kuske
Constraint Satisfaction Problems and Finite Algebras
Andrei Bulatov, Andrei Krokhin, Peter Jeavons
Negation Elimination from Simple Equational Formulae
Reinhard Pichler