Peter Widmayer, Francisco Triguero Ruiz, Rafael Morales Bueno, Matthew Hennessy, Stephan Eidenbenz, Ricardo Conejo
Proceedings of the 29th International Colloquium on Automata, Languages and Programming
ICALP, 2002.

@proceedings{ICALP-2002,
	address       = "Malaga, Spain",
	editor        = "Peter Widmayer and Francisco Triguero Ruiz and Rafael Morales Bueno and Matthew Hennessy and Stephan Eidenbenz and Ricardo Conejo",
	isbn          = "3-540-43864-5",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 29th International Colloquium on Automata, Languages and Programming}",
	volume        = 2380,
	year          = 2002,
}

Contents (90 items)

10 ×#bound
9 ×#problem
7 ×#graph
6 ×#performance
5 ×#approximate
5 ×#automaton
5 ×#complexity
5 ×#on the
4 ×#algebra
4 ×#algorithm

ICALP-2002-Reif #assembly

Molecular Assembly and Computation: From Theory to Experimental Demonstrations (JHR), pp. 1–21.

ICALP-2002-Marathe #complexity #predict #towards

Towards a Predictive Computational Complexity Theory (MVM), pp. 22–31.

ICALP-2002-Pitts #semantics #syntax

Equivariant Syntax and Semantics (AMP), pp. 32–36.

ICALP-2002-Senizergues #decidability

L(A) = L(B)? Decidability Results from Complete Formal Systems (GS), p. 37.

ICALP-2002-LungoFNV #constraints #re-engineering

Discrete Tomography: Reconstruction under Periodicity Constraints (ADL, AF, MN, LV), pp. 38–56.

ICALP-2002-Mannila #data mining #mining #problem

Local and Global Methods in Data Mining: Basic Techniques and Open Problems (HM), pp. 57–68.

ICALP-2002-HermenegildoPBL #approximate #debugging #semantics #specification #using #validation

Program Debugging and Validation Using Semantic Approximations and Partial Specifications (MVH, GP, FB, PLG), pp. 69–72.

ICALP-2002-EngebretsenHR #equation #finite

Inapproximability Results for Equations over Finite Groups (LE, JH, AR), pp. 73–84.

ICALP-2002-Pettie #algorithm #graph #performance

A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs (SP), pp. 85–97.

ICALP-2002-Colcombet #decidability #first-order #graph #on the #product line #reachability

On Families of Graphs Having a Decidable First Order Theory with Reachability (TC), pp. 98–109.

ICALP-2002-FabrikantKP #internet #paradigm #trade-off

Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet (AF, EK, CHP), pp. 110–122.

ICALP-2002-FotakisKKMS #complexity #game studies #nash

The Structure and Complexity of Nash Equilibria for a Selfish Routing Game (DF, SCK, EK, MM, PGS), pp. 123–134.

ICALP-2002-KhannaNR #communication #protocol

Control Message Aggregation in Group Communication Protocols (SK, JN, DR), pp. 135–146.

ICALP-2002-JurdzinskiL

Church-Rosser Languages vs. UCFL (TJ, KL), pp. 147–158.

ICALP-2002-Bala #regular expression

Intersection of Regular Languages and Star Hierarchy (SB), pp. 159–169.

ICALP-2002-Lombardy #automaton #on the

On the Construction of Reversible Automata for Reversible Languages (SL), pp. 170–182.

ICALP-2002-Elmasry #adaptation #sorting

Priority Queues, Pairing, and Adaptive Sorting (AE), pp. 183–194.

ICALP-2002-BenderCR #algorithm #exponential #performance

Exponential Structures for Efficient Cache-Oblivious Algorithms (MAB, RC, RR), pp. 195–207.

ICALP-2002-ImpagliazzoS #axiom #bound #simulation

Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations (RI, NS), pp. 208–219.

ICALP-2002-EstebanGM #bound #complexity #on the

On the Complexity of Resolution with Bounded Conjunctions (JLE, NG, JM), pp. 220–231.

ICALP-2002-KiayiasY #encryption

Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes (AK, MY), pp. 232–243.

ICALP-2002-IshaiK

Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials (YI, EK), pp. 244–256.

ICALP-2002-GrigorievHP #algebra #bound #exponential #proving

Exponential Lower Bound for Static Semi-algebraic Proofs (DG, EAH, DVP), pp. 257–268.

ICALP-2002-JakobyL #problem #symmetry

Paths Problems in Symmetric Logarithmic Space (AJ, ML), pp. 269–280.

ICALP-2002-Damaschke #scheduling

Scheduling Search Procedures (PD), pp. 281–292.

ICALP-2002-IwamaT #online #problem

Removable Online Knapsack Problems (KI, ST), pp. 293–305.

ICALP-2002-EpsteinSS #bound #online

New Bounds for Variable-Sized and Resource Augmented Online Bin Packing (LE, SSS, RvS), pp. 306–317.

ICALP-2002-Ollinger #automaton

The Quest for Small Universal Cellular Automata (NO), pp. 318–329.

ICALP-2002-PapazianR #automaton #graph #recognition

Hyperbolic Recognition by Graph Automata (CP, ER), pp. 330–342.

ICALP-2002-AblayevMP #bound #branch #probability #quantum #source code

Quantum and Stochastic Branching Programs of Bounded Width (FMA, CM, CP), pp. 343–354.

ICALP-2002-GarganoHSV #bound #branch

Spanning Trees with Bounded Number of Branch Vertices (LG, PH, LS, UV), pp. 355–365.

ICALP-2002-BeierSS #data type #energy #geometry #network #using

Energy Optimal Routing in Radio Networks Using Geometric Data Structures (RB, PS, NS), pp. 366–376.

ICALP-2002-ChristerssonGL #ad hoc #bound #network

Gossiping with Bounded Size Messages in ad hoc Radio Networks (MC, LG, AL), pp. 377–389.

ICALP-2002-Merkle #probability #sequence

The Kolmogorov-Loveland Stochastic Sequences Are Not Closed under Selecting Subsequences (WM), pp. 390–400.

ICALP-2002-HearnD #constraints #logic #nondeterminism #reduction

The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications (RAH, EDD), pp. 401–413.

ICALP-2002-Dalmau #constraints #nondeterminism #problem

Constraint Satisfaction Problems in Non-deterministic Logarithmic Space (VD), pp. 414–425.

ICALP-2002-BrodalF

Cache Oblivious Distribution Sweeping (GSB, RF), pp. 426–438.

ICALP-2002-OstlinP

One-Probe Search (AÖ, RP), pp. 439–450.

ICALP-2002-CharikarIP #algorithm #orthogonal #problem #query #set

New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems (MC, PI, RP), pp. 451–462.

ICALP-2002-MartinMW #probability

Measuring the Probabilistic Powerdomain (KM, MWM, JW), pp. 463–475.

ICALP-2002-OngG #game studies

Games Characterizing Levy-Longo Trees (CHLO, PDG), pp. 476–487.

ICALP-2002-BauerES #functional #paradigm

Comparing Functional Paradigms for Exact Real-Number Computation (AB, MHE, AKS), pp. 488–500.

ICALP-2002-DuchonFLS #random

Random Sampling from Boltzmann Principles (PD, PF, GL, GS), pp. 501–513.

ICALP-2002-DuchM #data type #multi #on the #orthogonal #performance

On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures (AD, CM), pp. 514–524.

ICALP-2002-Kick #algebra #modelling #process

Bialgebraic Modelling of Timed Processes (MK), pp. 525–536.

ICALP-2002-BreugelSW #markov #process #testing

Testing Labelled Markov Processes (FvB, SS, JW), pp. 537–548.

ICALP-2002-HitchcockL #complexity #strict #why

Why Computational Complexity Requires Stricter Martingales (JMH, JHL), pp. 549–560.

ICALP-2002-Hitchcock #effectiveness

Correspondence Principles for Effective Dimensions (JMH), pp. 561–571.

ICALP-2002-MeseguerR #algebra #approach #specification

A Total Approach to Partial Algebraic Specification (JM, GR), pp. 572–584.

ICALP-2002-LohreyDH #axiom

Axiomatising Divergence (ML, PRD, HH), pp. 585–596.

ICALP-2002-CardelliGG #graph #logic #query

A Spatial Logic for Querying Graphs (LC, PG, GG), pp. 597–610.

ICALP-2002-Radzik #bound #network

Improving Time Bounds on Maximum Generalised Flow Computations by Contracting the Network (TR), pp. 611–622.

ICALP-2002-BermanK #approximate #bound

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION (PB, MK), pp. 623–632.

ICALP-2002-DemetrescuI #bound #trade-off

Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths (CD, GFI), pp. 633–643.

ICALP-2002-HenzingerKKM #synthesis

Synthesis of Uninitialized Systems (TAH, SCK, OK, FYCM), pp. 644–656.

ICALP-2002-GenestMSZ #infinity #model checking

Infinite-State High-Level MSCs: Model-Checking and Realizability (BG, AM, HS, MZ), pp. 657–668.

ICALP-2002-Wich #ambiguity

Universal Inherence of Cycle-Free Context-Free Ambiguity Functions (KW), pp. 669–680.

ICALP-2002-GuhaIMS #data type #performance

Histogramming Data Streams with Fast Per-Item Processing (SG, PI, SM, MS), pp. 681–692.

ICALP-2002-CharikarCF #data type

Finding Frequent Items in Data Streams (MC, KCC, MFC), pp. 693–703.

ICALP-2002-Cachat #automaton #game studies #graph #synthesis

Symbolic Strategy Synthesis for Games on Pushdown Graphs (TC), pp. 704–715.

ICALP-2002-Srba #algebra #process #similarity

Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard (JS), pp. 716–727.

ICALP-2002-BrodalLOP #problem #statistics #string

Solving the String Statistics Problem in Time O(n log n) (GSB, RBL, AÖ, CNSP), pp. 728–739.

ICALP-2002-DengLLMW #string

A PTAS for Distinguishing (Sub)string Selection (XD, GL, ZL, BM, LW), pp. 740–751.

ICALP-2002-KuskeL #formal method #monad #on the

On the Theory of One-Step Rewriting in Trace Monoids (DK, ML), pp. 752–763.

ICALP-2002-BieleckiHPTB #navigation

Navigating with a Browser (MB, JH, JP, JT, JVdB), pp. 764–775.

ICALP-2002-KumarM #scheduling

Improved Results for Stackelberg Scheduling Strategies (VSAK, MVM), pp. 776–787.

ICALP-2002-AdamyAAE

Call Control in Rings (UA, CA, RSA, TE), pp. 788–799.

ICALP-2002-ChrobakENSSTV #scheduling

Preemptive Scheduling in Overloaded Systems (MC, LE, JN, JS, RvS, TT, NV), pp. 800–811.

ICALP-2002-KarhumakiL #equivalence #finite #problem

The Equivalence Problem of Finite Substitutions on ab*c, with Applications (JK, LPL), pp. 812–820.

ICALP-2002-Stirling #equivalence #recursion

Deciding DPDA Equivalence Is Primitive Recursive (CS), pp. 821–832.

ICALP-2002-Bojanczyk #automaton #finite #modelling

Two-Way Alternating Automata and Finite Models (MB), pp. 833–844.

ICALP-2002-BermanKN #approximate #parallel

Approximating Huffman Codes in Parallel (PB, MK, YN), pp. 845–855.

ICALP-2002-FantozziPP #integration #memory management #parallel

Seamless Integration of Parallelism and Memory Hierarchy (CF, AP, GP), pp. 856–867.

ICALP-2002-Nisan #approximate #communication #complexity #set

The Communication Complexity of Approximate Set Packing and Covering (NN), pp. 868–875.

ICALP-2002-Doerr #game studies

Antirandomizing the Wrong Game (BD), pp. 876–887.

ICALP-2002-AkcogluDK #performance

Fast Universalization of Investment Strategies with Provably Good Relative Returns (KA, PD, MYK), pp. 888–900.

ICALP-2002-AdlerRSSV #graph #random

Randomized Pursuit-Evasion in Graphs (MA, HR, NS, CS, BV), pp. 901–912.

ICALP-2002-Wells

The Essence of Principal Typings (JBW), pp. 913–925.

ICALP-2002-AdsulS #linear #logic

Complete and Tractable Local Linear Time Temporal Logics over Traces (BA, MAS), pp. 926–937.

ICALP-2002-GastinM #logic

An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces (PG, MM), pp. 938–949.

ICALP-2002-Brattka #random #recursion #set

Random Numbers and an Incomplete Immune Recursive Set (VB), pp. 950–961.

ICALP-2002-Hertling #markov

A Banach-Mazur Computable But Not Markov Computable Function on the Computable Real Numbers (PH), pp. 962–972.

ICALP-2002-CzumajLZ #approximate #design #network #polynomial #problem

Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem (AC, AL, HZ), pp. 973–984.

ICALP-2002-BjorklundH

Finding a Path of Superlogarithmic Length (AB, TH), pp. 985–992.

ICALP-2002-Uehara #algorithm #graph #linear

Linear Time Algorithms on Chordal Bipartite and Strongly Chordal Graphs (RU), pp. 993–1004.

ICALP-2002-Holmerin

Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs (JH), pp. 1005–1016.

ICALP-2002-KohayakawaNR #performance #testing

Efficient Testing of Hypergraphs (YK, BN, VR), pp. 1017–1028.

ICALP-2002-WuC #problem

Optimal Net Surface Problems with Applications (XW, DZC), pp. 1029–1042.

ICALP-2002-BonichonSM #theorem

Wagner’s Theorem on Realizers (NB, BLS, MM), pp. 1043–1053.

ICALP-2002-Liberatore

Circular Arrangements (VL), pp. 1054–1066.