Ugo Montanari, José D. P. Rolim, Emo Welzl
Proceedings of the 27th International Colloquium on Automata, Languages and Programming
ICALP, 2000.

@proceedings{ICALP-2000,
	address       = "Geneva, Switzerland",
	editor        = "Ugo Montanari and José D. P. Rolim and Emo Welzl",
	isbn          = "3-540-67715-1",
	publisher     = "{Springer-Verlag}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 27th International Colloquium on Automata, Languages and Programming}",
	volume        = 1853,
	year          = 2000,
}

Contents (78 items)

10 ×#algorithm
8 ×#problem
7 ×#on the
6 ×#approximate
6 ×#bound
6 ×#multi
5 ×#finite
5 ×#graph
5 ×#logic
4 ×#performance

ICALP-2000-Abramsky #game studies #semantics

Game Semantics: Achievements and Prospects (SA), p. 1.

ICALP-2000-EngebretsenH #approximate #clique

Clique Is Hard to Approximate within n1-o(1) (LE, JH), pp. 2–12.

ICALP-2000-KrivelevichV #approximate #independence

Approximating the Independence Number and the Chromatic Number in Expected Polynominal Time (MK, VHV), pp. 13–24.

ICALP-2000-CalcagnoMT #approach #imperative #multi #programming

Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming (CC, EM, WT), pp. 25–36.

ICALP-2000-MycroftS #functional #parallel

A Statically Allocated Parallel Functional Language (AM, RS), pp. 37–48.

ICALP-2000-PettieR #algorithm

An Optimal Minimum Spanning Tree Algorithm (SP, VR), pp. 49–60.

ICALP-2000-Hagerup #ram #word

Improved Shortest Paths on the Word RAM (TH), pp. 61–72.

ICALP-2000-AlstrupH #algorithm

Improved Algorithms for Finding Level Ancestors in Dynamic Trees (SA, JH), pp. 73–84.

ICALP-2000-PlotkinPST #logic

Lax Logical Relations (GDP, JP, DS, RDT), pp. 85–102.

ICALP-2000-GhicaM #algol #reasoning #regular expression #using

Reasoning about Idealized ALGOL Using Regular Languages (DRG, GM), pp. 103–115.

ICALP-2000-Martin #metric #process

The Measurement Process in Domain Theory (KM), pp. 116–126.

ICALP-2000-EngelsH #concept #evolution #framework #graph transformation #modelling

Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution (GE, RH), pp. 127–150.

ICALP-2000-AtseriasGG #principle #proving

Monotone Proofs of the Pigeon Hole Principle (AA, NG, RG), pp. 151–162.

ICALP-2000-LuttgenM #modelling #semantics

Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models (GL, MM), pp. 163–174.

ICALP-2000-BruniS #algebra #modelling

Algebraic Models for Contextual Nets (RB, VS), pp. 175–186.

ICALP-2000-BolligW #bound #problem

Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems (BB, IW), pp. 187–198.

ICALP-2000-HromkovicKKSS #automaton #finite #metric #nondeterminism

Measures of Nondeterminism in Finite Automata (JH, JK, HK, GS, SS), pp. 199–210.

ICALP-2000-DiekertG #ltl

LTL Is Expressively Complete for Mazurkiewicz Traces (VD, PG), pp. 211–222.

ICALP-2000-Moszkowski #logic #proving

An Automata-Theoretic Completeness Proof for Interval Temporal Logic (BCM), pp. 223–234.

ICALP-2000-Hastad #algorithm #approximate #np-hard #optimisation #performance #problem #question

Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? (JH), p. 235.

ICALP-2000-DantsinGHS #algorithm #satisfiability

Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search (ED, AG, EAH, US), pp. 236–247.

ICALP-2000-Blomer

Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices (JB), pp. 248–259.

ICALP-2000-Libkin #constraints #independence #quantifier

Variable Independence, Quantifier Elimination, and Constraint Representations (LL), pp. 260–271.

ICALP-2000-BulatovKJ #algebra #constraints #finite #problem

Constraint Satisfaction Problems and Finite Algebras (AAB, AAK, PJ), pp. 272–282.

ICALP-2000-Seiden #algorithm #bound #online

An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing (SSS), pp. 283–295.

ICALP-2000-CsirikW #bound #online

Resource Augmentation for Online Bounded Space Bin Packing (JC, GJW), pp. 296–304.

ICALP-2000-AmbuhlGS #algorithm #problem

Optimal Projective Algorithms for the List Update Problem (CA, BG, BvS), pp. 305–316.

ICALP-2000-Kucera #algorithm #performance #process #verification

Efficient Verification Algorithms for One-Counter Processes (AK), pp. 317–328.

ICALP-2000-Mayr #bisimulation #complexity #on the #parallel #problem #process

On the Complexity of Bisimulation Problems for Basic Parallel Processes (RM), pp. 329–341.

ICALP-2000-LugiezS #decidability #first-order #logic

Decidable First-Order Transition Logics for PA-Processes (DL, PS), pp. 342–353.

ICALP-2000-FocardiGM #analysis #encryption #protocol

Non Interference for the Analysis of Cryptographic Protocols (RF, RG, FM), pp. 354–372.

ICALP-2000-AkhaviV #algorithm

Average Bit-Complexity of Euclidean Algorithms (AA, BV), pp. 373–387.

ICALP-2000-BanderierFSS

Planar Maps and Airy Phenomena (CB, PF, GS, MS), pp. 388–402.

ICALP-2000-Konig #mobile #process #type system

Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System (BK0), pp. 403–414.

ICALP-2000-HennessyR #data flow #resource management #π-calculus

Information Flow vs. Resource Access in the Asynchronous π-Calculus (MH, JR), pp. 415–427.

ICALP-2000-Karp #algorithm #challenge #research

The Genomics Revolution and Its Challenges for Algorithmic Research (RMK), p. 428.

ICALP-2000-MannaS #safety

Alternating the Temporal Picture for Safety (ZM, HS), pp. 429–450.

ICALP-2000-SantisCP #proving

Necessary and Sufficient Assumptions for Non-iterative Zero-Knowledge Proofs of Knowledge for All NP Relations (ADS, GDC, GP), pp. 451–462.

ICALP-2000-AielloBOR #performance #proving #verification

Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP (WA, SNB, RO, SR), pp. 463–474.

ICALP-2000-EsparzaH #approach #ltl #model checking

A New Unfolding Approach to LTL Model Checking (JE, KH), pp. 475–486.

ICALP-2000-MeenakshiR #finite #message passing #reasoning

Reasoning about Message Passing in Finite State Environments (BM, RR), pp. 487–498.

ICALP-2000-BaudronPS #multi #security

Extended Notions of Security for Multicast Public Key Cryptosystems (OB, DP, JS), pp. 499–511.

ICALP-2000-CachinCKM #mobile

One-Round Secure Computation and Secure Autonomous Mobile Agents (CC, JC, JK, JM), pp. 512–523.

ICALP-2000-Baum-WaidnerW #contract #multi

Round-Optimal and Abuse Free Optimistic Multi-party Contract Signing (BBW, MW), pp. 524–535.

ICALP-2000-KarhumakiP #finite #on the #set

On the Centralizer of a Finite Set (JK, IP), pp. 536–546.

ICALP-2000-NevenS #automaton #on the #power of

On the Power of Tree-Walking Automata (FN, TS), pp. 547–560.

ICALP-2000-BealC #infinity #transducer #word

Determinization of Transducers over Infinite Words (MPB, OC), pp. 561–570.

ICALP-2000-Mehlhorn #algorithm #constraints #graph #programming

Constraint Programming and Graph Algorithms (KM), pp. 571–575.

ICALP-2000-AlonKKMS #scalability

Scalable Secure Storage when Half the System Is Faulty (NA, HK, MK, DM, JPS), pp. 576–587.

ICALP-2000-BorosGKM #generative #multi

Generating Partial and Multiple Transversals of a Hypergraph (EB, VG, LK, KM), pp. 588–599.

ICALP-2000-Santo #normalisation

Revisiting the Correspondence between Cut Elimination and Normalisation (JES), pp. 600–611.

ICALP-2000-Pichler #equation

Negation Elimination from Simple Equational Formulae (RP), pp. 612–623.

ICALP-2000-KumarAR #set

Hardness of Set Cover with Intersection 1 (VSAK, SA, HR), pp. 624–635.

ICALP-2000-ElkinP #problem

Strong Inapproximability of the Basic k-Spanner Problem (ME, DP), pp. 636–647.

ICALP-2000-Kuske #infinity #logic

Infinite Series-Parallel Posets: Logic and Languages (DK), pp. 648–662.

ICALP-2000-Urbanski #automaton #on the

On Deciding if Deterministic Rabin Language Is in Büchi Class (TFU), pp. 663–674.

ICALP-2000-HenriksenMKT #graph #on the #sequence

On Message Sequence Graphs and Finitely Generated Regular MSC Languages (JGH, MM, KNK, PST), pp. 675–686.

ICALP-2000-Goldreich #pseudo

Pseudorandomness (OG), pp. 687–704.

ICALP-2000-GoldbergJKP #bound #capacity #protocol

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols (LAG, MJ, SK, MP), pp. 705–716.

ICALP-2000-ChlebusGOR

Deterministic Radio Broadcasting (BSC, LG, AÖ, JMR), pp. 717–728.

ICALP-2000-FokkinkL #equation #specification

An ω-Complete Equational Specification of Interleaving (WF, SPL), pp. 729–743.

ICALP-2000-BravettiG #axiom #behaviour #congruence #finite

A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors (MB, RG), pp. 744–755.

ICALP-2000-AdlerFGP #bound

Tight Size Bounds for Packet Headers in Narrow Meshes (MA, FEF, LAG, MP), pp. 756–767.

ICALP-2000-MargaraS #network #problem

Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link (LM, JS), pp. 768–779.

ICALP-2000-BaierHHK #logic #on the

On the Logical Characterisation of Performability Properties (CB, BRH, HH, JPK), pp. 780–792.

ICALP-2000-BournezM #on the #representation

On the Representation of Timed Polyhedra (OB, OM), pp. 793–807.

ICALP-2000-Broder #independence #permutation #theory and practice

Min-wise Independent Permutations: Theory and Practice (AZB), p. 808.

ICALP-2000-BenderR #graph #sublinear #testing

Testing Acyclicity of Directed Graphs in Sublinear Time (MAB, DR), pp. 809–820.

ICALP-2000-Djidjev #graph

Computing the Girth of a Planar Graph (HD), pp. 821–831.

ICALP-2000-FournierK #bound

Lower Bounds Are Not Easier over the Reals: Inside PH (HF, PK), pp. 832–843.

ICALP-2000-BaligaCMS

Unlearning Helps (GB, JC, WM, FS), pp. 844–855.

ICALP-2000-CzumajL #approximate #multi #performance #problem

Fast Approximation Schemes for Euclidean Multi-connectivity Problems (AC, AL), pp. 856–868.

ICALP-2000-Grigni #approximate #graph

Approximate TSP in Graphs with Forbidden Minors (MG), pp. 869–877.

ICALP-2000-JansenP #approximate #multi #scheduling

Polynominal Time Approximation Schemes for General Multiprocessor Job Shop Scheduling (KJ, LP), pp. 878–889.

ICALP-2000-McKenzieSTV

The Many Faces of a Translation (PM, TS, DT, HV), pp. 890–901.

ICALP-2000-Lutz #sequence

Gales and the Constructive Dimension of Individual Sequences (JHL), pp. 902–913.

ICALP-2000-Merkle #power of #query

The Global Power of Additional Queries to p-Random Oracles (WM), pp. 914–925.

ICALP-2000-Buresh-OppenheimCIP #calculus

Homogenization and the Polynominal Calculus (JBO, MC, RI, TP), pp. 926–937.