Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger
Proceedings of the 30th International Colloquium on Automata, Languages and Programming
ICALP, 2003.

@proceedings{ICALP-2003,
	address       = "Eindhoven, The Netherlands",
	editor        = "Jos C. M. Baeten and Jan Karel Lenstra and Joachim Parrow and Gerhard J. Woeginger",
	isbn          = "3-540-40493-7",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 30th International Colloquium on Automata, Languages and Programming}",
	volume        = 2719,
	year          = 2003,
}

Contents (90 items)

13 ×#algorithm
11 ×#problem
10 ×#graph
9 ×#approximate
7 ×#automaton
6 ×#complexity
5 ×#multi
4 ×#performance
4 ×#probability
3 ×#bisimulation

ICALP-2003-BergstraB #algebra #equivalence #process

Polarized Process Algebra and Program Equivalence (JAB, IB), pp. 1–21.

ICALP-2003-Condon #design #predict #problem

Problems on RNA Secondary Structure Prediction and Design (AC), pp. 22–32.

ICALP-2003-Fiat #network

Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks (AF), p. 33.

ICALP-2003-Mutzel #data type #graph

The SPQR-Tree Data Structure in Graph Drawing (PM), pp. 34–46.

ICALP-2003-Peled #model checking #testing

Model Checking and Testing Combined (DP), pp. 47–63.

ICALP-2003-Vardi #automaton #logic

Logic and Automata: A Match Made in Heaven (MYV), pp. 64–65.

ICALP-2003-HromkovicS #automaton #comparison #multi

Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes (JH, GS), pp. 66–80.

ICALP-2003-BonisGV #framework #testing

Generalized Framework for Selectors with Applications in Optimal Group Testing (ADB, LG, UV), pp. 81–96.

ICALP-2003-BleichenbacherKY #semistructured data

Decoding of Interleaved Reed Solomon Codes over Noisy Data (DB, AK, MY), pp. 97–108.

ICALP-2003-BlomFN #axiom #on the #simulation

On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces (SB, WF, SN), pp. 109–118.

ICALP-2003-GorlaP #resource management

Resource Access and Mobility Control with Dynamic Privileges Acquisition (DG, RP), pp. 119–132.

ICALP-2003-BusiGZ #calculus #recursion #replication

Replication vs. Recursive Definitions in Channel Based Calculi (NB, MG, GZ), pp. 133–144.

ICALP-2003-AgeevYZ #algorithm #approximate #combinator #problem

Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem (AAA, YY, JZ), pp. 145–156.

ICALP-2003-Blaser #algorithm #approximate #difference #symmetry

An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality (MB), pp. 157–163.

ICALP-2003-GandhiHKKS #algorithm #approximate

An Improved Approximation Algorithm for Vertex Cover with Hard Capacities (RG, EH, SK, GK, AS), pp. 164–175.

ICALP-2003-AroraC #approximate #problem #strict

Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem (SA, KLC), pp. 176–188.

ICALP-2003-ChekuriGN #approximate

Approximating Steiner k-Cuts (CC, SG, JN), pp. 189–199.

ICALP-2003-Coja-OghlanMS #approximate #graph #random

MAX k-CUT and Approximating the Chromatic Number of Random Graphs (ACO, CM, VS), pp. 200–211.

ICALP-2003-ElkinK #algorithm #approximate #multi #problem

Approximation Algorithm for Directed Telephone Multicast Problem (ME, GK), pp. 212–223.

ICALP-2003-AnconaFMZ #mixin

Mixin Modules and Computational Effects (DA, SF, EM, EZ), pp. 224–238.

ICALP-2003-Okhotin #equation #problem

Decision Problems for Language Equations with Boolean Operations (AO), pp. 239–251.

ICALP-2003-BruniM

Generalized Rewrite Theories (RB, JM), pp. 252–266.

ICALP-2003-AntunesF #revisited

Sophistication Revisited (LA, LF), pp. 267–277.

ICALP-2003-HitchcockLM #complexity

Scaled Dimension and Nonuniform Complexity (JMH, JHL, EM), pp. 278–290.

ICALP-2003-HoyerMW #bound #quantum

Quantum Search on Bounded-Error Inputs (PH, MM, RdW), pp. 291–299.

ICALP-2003-JainRS #communication #complexity #theorem

A Direct Sum Theorem in Communication Complexity via Message Compression (RJ, JR, PS), pp. 300–315.

ICALP-2003-FranceschiniG

Optimal Cache-Oblivious Implicit Dictionaries (GF, RG), pp. 316–331.

ICALP-2003-GalM #complexity #data type

The Cell Probe Complexity of Succinct Data Structures (AG, PBM), pp. 332–344.

ICALP-2003-MunroRRR #permutation

Succinct Representations of Permutations (JIM, RR, VR, SSR), pp. 345–356.

ICALP-2003-RamanR

Succinct Dynamic Dictionaries and Trees (RR, SSR), pp. 357–368.

ICALP-2003-KormanP

Labeling Schemes for Weighted Dynamic Trees (AK, DP), pp. 369–383.

ICALP-2003-BaswanaS #algorithm #graph #linear

A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n1+1/k) Size in Weighted Graphs (SB, SS), pp. 384–296.

ICALP-2003-HallHS #algorithm #complexity #multi #performance

Multicommodity Flows over Time: Efficient Algorithms and Complexity (AH, SH, MS), pp. 397–409.

ICALP-2003-ChekuriMS #multi

Multicommodity Demand Flow in a Tree (CC, MM, FBS), pp. 410–425.

ICALP-2003-DrosteK

Skew and Infinitary Formal Power Series (MD, DK), pp. 426–438.

ICALP-2003-HromkovicS03a #automaton #finite #nondeterminism

Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser’s Separation (JH, GS), pp. 439–451.

ICALP-2003-DenisE #automaton #probability

Residual Languages and Probabilistic Automata (FD, YE), pp. 452–463.

ICALP-2003-StoelingaV #automaton #probability #testing

A Testing Scenario for Probabilistic Automata (MS, FWV), pp. 464–477.

ICALP-2003-Senizergues #equivalence #problem

The Equivalence Problem for t-Turn DPDA Is Co-NP (GS), pp. 478–489.

ICALP-2003-HolzerK #automaton

Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k (MH, MK), pp. 490–501.

ICALP-2003-Even-DarKM #convergence #nash

Convergence Time to Nash Equilibria (EED, AK, YM), pp. 502–513.

ICALP-2003-FeldmannGLMR #coordination #game studies

Nashification and the Coordination Ratio for a Selfish Routing Game (RF, MG, TL, BM, MR), pp. 514–526.

ICALP-2003-BansalAM #multi #performance

Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution (VB, AA, VSM), pp. 527–542.

ICALP-2003-BorosEGKM #difference #generative #problem

An Intersection Inequality for Discrete Distributions and Related Generation Problems (EB, KME, VG, LK, KM), pp. 543–555.

ICALP-2003-Cachat #automaton #game studies #graph #higher-order

Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games (TC), pp. 556–569.

ICALP-2003-Mayr #bisimulation #equivalence #process

Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes (RM), pp. 570–583.

ICALP-2003-MerroN #bisimulation #mobile #proving

Bisimulation Proof Methods for Mobile Ambients (MM, FZN), pp. 584–598.

ICALP-2003-CarayolC #infinity #on the

On Equivalent Representations of Infinite Structures (AC, TC), pp. 599–610.

ICALP-2003-Schonhage #adaptation #optimisation #performance

Adaptive Raising Strategies Optimizing Relative Efficiency (AS), pp. 611–623.

ICALP-2003-SittersSP #algorithm #problem

A Competitive Algorithm for the General 2-Server Problem (RS, LS, WdP), pp. 624–636.

ICALP-2003-Fotakis #on the #online

On the Competitive Ratio for Online Facility Location (DF), pp. 637–652.

ICALP-2003-AlbersS #case study #documentation

A Study of Integrated Document and Connection Caching (SA, RvS), pp. 653–667.

ICALP-2003-XieDI #equation #infinity #polynomial #verification

A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems (GX, ZD, OHI), pp. 668–680.

ICALP-2003-KlaedtkeR #higher-order #logic #monad

Monadic Second-Order Logics with Cardinalities (FK, HR), pp. 681–696.

ICALP-2003-KupfermanV

Π₂ ∩ Σ₂ ≡ AFMC (OK, MYV), pp. 697–713.

ICALP-2003-RybinaV #bound #formal method

Upper Bounds for a Theory of Queues (TR, AV), pp. 714–724.

ICALP-2003-BergerBBCR #network

Degree Distribution of the FKP Network Model (NB, BB, CB, JTC, OR), pp. 725–738.

ICALP-2003-BlondelD #graph #matrix #similarity

Similarity Matrices for Pairs of Graphs (VDB, PVD), pp. 739–750.

ICALP-2003-BhatiaCFN #algorithm #aspect-oriented

Algorithmic Aspects of Bandwidth Trading (RB, JC, AF, JN), pp. 751–766.

ICALP-2003-JohannsenL #exponential

CTL+ Is Complete for Double Exponential Time (JJ, ML), pp. 767–775.

ICALP-2003-TorreNPP #recursion #state machine

Hierarchical and Recursive State Machines with Context-Dependent Properties (SLT, MN, MP, GP), pp. 776–789.

ICALP-2003-Schnoebelen #model checking

Oracle Circuits for Branching-Time Model Checking (PS), pp. 790–801.

ICALP-2003-GarganoH #graph #how

There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them) (LG, MH), pp. 802–816.

ICALP-2003-FialaP #complexity #problem

The Computational Complexity of the Role Assignment Problem (JF, DP), pp. 817–828.

ICALP-2003-DemaineFHT #algorithm #graph #parametricity

Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs (EDD, FVF, MTH, DMT), pp. 829–844.

ICALP-2003-ChenKPSX #complexity #graph #problem

Genus Characterizes the Complexity of Graph Problems: Some Tight Results (JC, IAK, LP, ES, GX), pp. 845–856.

ICALP-2003-EisnerFHMC

The Definition of a Temporal Clock Operator (CE, DF, JH, AM, DVC), pp. 857–870.

ICALP-2003-AriolaH #logic

Minimal Classical Logic and Control Operators (ZMA, HH), pp. 871–885.

ICALP-2003-HenzingerJM

Counterexample-Guided Control (TAH, RJ, RM), pp. 886–902.

ICALP-2003-Hannay #axiom #data type #higher-order

Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types (JEH), pp. 903–917.

ICALP-2003-MatiasP #performance #traversal

Efficient Pebbling for List Traversal Synopses (YM, EP), pp. 918–928.

ICALP-2003-AmirACLP #algorithm #bound

Function Matching: Algorithms, Applications, and a Lower Bound (AA, YA, RC, ML, EP), pp. 929–942.

ICALP-2003-KarkkainenS #array #linear

Simple Linear Work Suffix Array Construction (JK, PS), pp. 943–955.

ICALP-2003-GutierrezR #calculus #type system

Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems (FG, BCR), pp. 956–968.

ICALP-2003-BugliesiCPS #network

Secrecy in Untrusted Networks (MB, SC, AP, VS), pp. 969–983.

ICALP-2003-ChattopadhyayT #category theory #commutative

Locally Commutative Categories (AC, DT), pp. 984–995.

ICALP-2003-Doberkat #bisimulation #category theory #probability

Semi-pullbacks and Bisimulations in Categories of Stochastic Relations (EED), pp. 996–1007.

ICALP-2003-Rabinovich #analysis #probability

Quantitative Analysis of Probabilistic Lossy Channel Systems (AMR), pp. 1008–1021.

ICALP-2003-AlfaroHM

Discounting the Future in Systems Theory (LdA, TAH, RM), pp. 1022–1037.

ICALP-2003-AlfaroF #concurrent #data flow #game studies

Information Flow in Concurrent Games (LdA, MF), pp. 1038–1053.

ICALP-2003-IkedaKOY #finite #graph #random

Impact of Local Topological Information on Random Walks on Finite Graphs (SI, IK, NO, MY), pp. 1054–1067.

ICALP-2003-Jagerskupper #algorithm #analysis

Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces (JJ), pp. 1068–1079.

ICALP-2003-PoulalhonS

Optimal Coding and Sampling of Triangulations (DP, GS), pp. 1080–1094.

ICALP-2003-BodirskyGK #generative #graph #random

Generating Labeled Planar Graphs Uniformly at Random (MB, CG, MK), pp. 1095–1107.

ICALP-2003-CrescenziGNPU #online

Online Load Balancing Made Simple: Greedy Strikes Back (PC, GG, GN, PP, WU), pp. 1108–1122.

ICALP-2003-NaorST #realtime #scheduling

Real-Time Scheduling with a Budget (JN, HS, TT), pp. 1123–1137.

ICALP-2003-DeanG #algorithm #approximate #scheduling

Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling (BCD, MXG), pp. 1138–1152.

ICALP-2003-AwerbuchBS

Anycasting in Adversarial Systems: Routing and Admission Control (BA, AB, CS), pp. 1153–1168.

ICALP-2003-BespamyatnikhS #algorithm #approximate

Dynamic Algorithms for Approximating Interdistances (SB, MS), pp. 1169–1180.

ICALP-2003-CieliebakFPS #problem

Solving the Robots Gathering Problem (MC, PF, GP, NS), pp. 1181–1196.