27. ICALP 2000:
Geneva,
Switzerland
Ugo Montanari, José D. P. Rolim, Emo Welzl (Eds.):
Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000, Proceedings.
Lecture Notes in Computer Science 1853 Springer 2000, ISBN 3-540-67715-1 BibTeX
@proceedings{DBLP:conf/icalp/2000,
editor = {Ugo Montanari and
Jos{\'e} D. P. Rolim and
Emo Welzl},
title = {Automata, Languages and Programming, 27th International Colloquium,
ICALP 2000, Geneva, Switzerland, July 9-15, 2000, Proceedings},
booktitle = {ICALP},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {1853},
year = {2000},
isbn = {3-540-67715-1},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
- Samson Abramsky:
Game Semantics: Achievements and Prospects.
1
Electronic Edition (Springer LINK) BibTeX
- Lars Engebretsen, Jonas Holmerin:
Clique Is Hard to Approximate within n1-o(1).
2-12
Electronic Edition (Springer LINK) BibTeX
- Michael Krivelevich, Van H. Vu:
Approximating the Independence Number and the Chromatic Number in Expected Polynominal Time.
13-24
Electronic Edition (Springer LINK) BibTeX
- Cristiano Calcagno, Eugenio Moggi, Walid Taha:
Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming.
25-36
Electronic Edition (Springer LINK) BibTeX
- Alan Mycroft, Richard Sharp:
A Statically Allocated Parallel Functional Language.
37-48
Electronic Edition (Springer LINK) BibTeX
- Seth Pettie, Vijaya Ramachandran:
An Optimal Minimum Spanning Tree Algorithm.
49-60
Electronic Edition (Springer LINK) BibTeX
- Torben Hagerup:
Improved Shortest Paths on the Word RAM.
61-72
Electronic Edition (Springer LINK) BibTeX
- Stephen Alstrup, Jacob Holm:
Improved Algorithms for Finding Level Ancestors in Dynamic Trees.
73-84
Electronic Edition (Springer LINK) BibTeX
- Gordon D. Plotkin, John Power, Donald Sannella, Robert D. Tennent:
Lax Logical Relations.
85-102
Electronic Edition (Springer LINK) BibTeX
- Dan R. Ghica, Guy McCusker:
Reasoning about Idealized ALGOL Using Regular Languages.
103-115
Electronic Edition (Springer LINK) BibTeX
- Keye Martin:
The Measurement Process in Domain Theory.
116-126
Electronic Edition (Springer LINK) BibTeX
- Gregor Engels, Reiko Heckel:
Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution.
127-150
Electronic Edition (Springer LINK) BibTeX
- Albert Atserias, Nicola Galesi, Ricard Gavaldà:
Monotone Proofs of the Pigeon Hole Principle.
151-162
Electronic Edition (Springer LINK) BibTeX
- Gerald Lüttgen, Michael Mendler:
Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models.
163-174
Electronic Edition (Springer LINK) BibTeX
- Roberto Bruni, Vladimiro Sassone:
Algebraic Models for Contextual Nets.
175-186
Electronic Edition (Springer LINK) BibTeX
- Beate Bollig, Ingo Wegener:
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems.
187-198
Electronic Edition (Springer LINK) BibTeX
- Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert:
Measures of Nondeterminism in Finite Automata.
199-210
Electronic Edition (Springer LINK) BibTeX
- Volker Diekert, Paul Gastin:
LTL Is Expressively Complete for Mazurkiewicz Traces.
211-222
Electronic Edition (Springer LINK) BibTeX
- Ben C. Moszkowski:
An Automata-Theoretic Completeness Proof for Interval Temporal Logic.
223-234
Electronic Edition (Springer LINK) BibTeX
- Johan Håstad:
Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?
235
Electronic Edition (Springer LINK) BibTeX
- Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning:
Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search.
236-247
Electronic Edition (Springer LINK) BibTeX
- Johannes Blömer:
Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices.
248-259
Electronic Edition (Springer LINK) BibTeX
- Leonid Libkin:
Variable Independence, Quantifier Elimination, and Constraint Representations.
260-271
Electronic Edition (Springer LINK) BibTeX
- Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons:
Constraint Satisfaction Problems and Finite Algebras.
272-282
Electronic Edition (Springer LINK) BibTeX
- Steven S. Seiden:
An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing.
283-295
Electronic Edition (Springer LINK) BibTeX
- János Csirik, Gerhard J. Woeginger:
Resource Augmentation for Online Bounded Space Bin Packing.
296-304
Electronic Edition (Springer LINK) BibTeX
- Christoph Ambühl, Bernd Gärtner, Bernhard von Stengel:
Optimal Projective Algorithms for the List Update Problem.
305-316
Electronic Edition (Springer LINK) BibTeX
- Antonín Kucera:
Efficient Verification Algorithms for One-Counter Processes.
317-328
Electronic Edition (Springer LINK) BibTeX
- Richard Mayr:
On the Complexity of Bisimulation Problems for Basic Parallel Processes.
329-341
Electronic Edition (Springer LINK) BibTeX
- Denis Lugiez, Ph. Schnoebelen:
Decidable First-Order Transition Logics for PA-Processes.
342-353
Electronic Edition (Springer LINK) BibTeX
- Riccardo Focardi, Roberto Gorrieri, Fabio Martinelli:
Non Interference for the Analysis of Cryptographic Protocols.
354-372
Electronic Edition (Springer LINK) BibTeX
- Ali Akhavi, Brigitte Vallée:
Average Bit-Complexity of Euclidean Algorithms.
373-387
Electronic Edition (Springer LINK) BibTeX
- Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michèle Soria:
Planar Maps and Airy Phenomena.
388-402
Electronic Edition (Springer LINK) BibTeX
- Barbara König:
Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System.
403-414
Electronic Edition (Springer LINK) BibTeX
- Matthew Hennessy, James Riely:
Information Flow vs. Resource Access in the Asynchronous Pi-Calculus.
415-427
Electronic Edition (Springer LINK) BibTeX
- Richard M. Karp:
The Genomics Revolution and Its Challenges for Algorithmic Research.
428
Electronic Edition (Springer LINK) BibTeX
- Zohar Manna, Henny Sipma:
Alternating the Temporal Picture for Safety.
429-450
Electronic Edition (Springer LINK) BibTeX
- Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano:
Necessary and Sufficient Assumptions for Non-iterative Zero-Knowledge Proofs of Knowledge for All NP Relations.
451-462
Electronic Edition (Springer LINK) BibTeX
- William Aiello, Sandeep N. Bhatt, Rafail Ostrovsky, Sivaramakrishnan Rajagopalan:
Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP.
463-474
Electronic Edition (Springer LINK) BibTeX
- Javier Esparza, Keijo Heljanko:
A New Unfolding Approach to LTL Model Checking.
475-486
Electronic Edition (Springer LINK) BibTeX
- B. Meenakshi, Ramaswamy Ramanujam:
Reasoning about Message Passing in Finite State Environments.
487-498
Electronic Edition (Springer LINK) BibTeX
- Olivier Baudron, David Pointcheval, Jacques Stern:
Extended Notions of Security for Multicast Public Key Cryptosystems.
499-511
Electronic Edition (Springer LINK) BibTeX
- Christian Cachin, Jan Camenisch, Joe Kilian, Joy Müller:
One-Round Secure Computation and Secure Autonomous Mobile Agents.
512-523
Electronic Edition (Springer LINK) BibTeX
- Birgit Baum-Waidner, Michael Waidner:
Round-Optimal and Abuse Free Optimistic Multi-party Contract Signing.
524-535
Electronic Edition (Springer LINK) BibTeX
- Juhani Karhumäki, Ion Petre:
On the Centralizer of a Finite Set.
536-546
Electronic Edition (Springer LINK) BibTeX
- Frank Neven, Thomas Schwentick:
On the Power of Tree-Walking Automata.
547-560
Electronic Edition (Springer LINK) BibTeX
- Marie-Pierre Béal, Olivier Carton:
Determinization of Transducers over Infinite Words.
561-570
Electronic Edition (Springer LINK) BibTeX
- Kurt Mehlhorn:
Constraint Programming and Graph Algorithms.
571-575
Electronic Edition (Springer LINK) BibTeX
- Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien P. Stern:
Scalable Secure Storage when Half the System Is Faulty.
576-587
Electronic Edition (Springer LINK) BibTeX
- Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
Generating Partial and Multiple Transversals of a Hypergraph.
588-599
Electronic Edition (Springer LINK) BibTeX
- José Espírito Santo:
Revisiting the Correspondence between Cut Elimination and Normalisation.
600-611
Electronic Edition (Springer LINK) BibTeX
- Reinhard Pichler:
Negation Elimination from Simple Equational Formulae.
612-623
Electronic Edition (Springer LINK) BibTeX
- V. S. Anil Kumar, Sunil Arya, H. Ramesh:
Hardness of Set Cover with Intersection 1.
624-635
Electronic Edition (Springer LINK) BibTeX
- Michael Elkin, David Peleg:
Strong Inapproximability of the Basic k-Spanner Problem.
636-647
Electronic Edition (Springer LINK) BibTeX
- Dietrich Kuske:
Infinite Series-Parallel Posets: Logic and Languages.
648-662
Electronic Edition (Springer LINK) BibTeX
- Tomasz Fryderyk Urbanski:
On Deciding if Deterministic Rabin Language Is in Büchi Class.
663-674
Electronic Edition (Springer LINK) BibTeX
- Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P. S. Thiagarajan:
On Message Sequence Graphs and Finitely Generated Regular MSC Languages.
675-686
Electronic Edition (Springer LINK) BibTeX
- Oded Goldreich:
Pseudorandomness.
687-704
Electronic Edition (Springer LINK) BibTeX
- Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson:
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.
705-716
Electronic Edition (Springer LINK) BibTeX
- Bogdan S. Chlebus, Leszek Gasieniec, Anna Östlin, John Michael Robson:
Deterministic Radio Broadcasting.
717-728
Electronic Edition (Springer LINK) BibTeX
- Wan Fokkink, S. P. Luttik:
An omega-Complete Equational Specification of Interleaving.
729-743
Electronic Edition (Springer LINK) BibTeX
- Mario Bravetti, Roberto Gorrieri:
A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors.
744-755
Electronic Edition (Springer LINK) BibTeX
- Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson:
Tight Size Bounds for Packet Headers in Narrow Meshes.
756-767
Electronic Edition (Springer LINK) BibTeX
- Luciano Margara, Janos Simon:
Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link.
768-779
Electronic Edition (Springer LINK) BibTeX
- Christel Baier, Boudewijn R. Haverkort, Holger Hermanns, Joost-Pieter Katoen:
On the Logical Characterisation of Performability Properties.
780-792
Electronic Edition (Springer LINK) BibTeX
- Olivier Bournez, Oded Maler:
On the Representation of Timed Polyhedra.
793-807
Electronic Edition (Springer LINK) BibTeX
- Andrei Z. Broder:
Min-wise Independent Permutations: Theory and Practice.
808
Electronic Edition (Springer LINK) BibTeX
- Michael A. Bender, Dana Ron:
Testing Acyclicity of Directed Graphs in Sublinear Time.
809-820
Electronic Edition (Springer LINK) BibTeX
- Hristo Djidjev:
Computing the Girth of a Planar Graph.
821-831
Electronic Edition (Springer LINK) BibTeX
- Hervé Fournier, Pascal Koiran:
Lower Bounds Are Not Easier over the Reals: Inside PH.
832-843
Electronic Edition (Springer LINK) BibTeX
- Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan:
Unlearning Helps.
844-855
Electronic Edition (Springer LINK) BibTeX
- Artur Czumaj, Andrzej Lingas:
Fast Approximation Schemes for Euclidean Multi-connectivity Problems.
856-868
Electronic Edition (Springer LINK) BibTeX
- Michelangelo Grigni:
Approximate TSP in Graphs with Forbidden Minors.
869-877
Electronic Edition (Springer LINK) BibTeX
- Klaus Jansen, Lorant Porkolab:
Polynominal Time Approximation Schemes for General Multiprocessor Job Shop Scheduling.
878-889
Electronic Edition (Springer LINK) BibTeX
- Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer:
The Many Faces of a Translation.
890-901
Electronic Edition (Springer LINK) BibTeX
- Jack H. Lutz:
Gales and the Constructive Dimension of Individual Sequences.
902-913
Electronic Edition (Springer LINK) BibTeX
- Wolfgang Merkle:
The Global Power of Additional Queries to p-Random Oracles.
914-925
Electronic Edition (Springer LINK) BibTeX
- Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi:
Homogenization and the Polynominal Calculus.
926-937
Electronic Edition (Springer LINK) BibTeX
Copyright © Sat May 16 23:16:06 2009
by Michael Ley (ley@uni-trier.de)
