Fernando Orejas, Paul G. Spirakis, Jan van Leeuwen
Proceedings of the 28th International Colloquium on Automata, Languages and Programming
ICALP, 2001.

@proceedings{ICALP-2001,
	address       = "Crete, Greece",
	editor        = "Fernando Orejas and Paul G. Spirakis and Jan van Leeuwen",
	isbn          = "3-540-42287-0",
	publisher     = "{Springer-Verlag}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 28th International Colloquium on Automata, Languages and Programming}",
	volume        = 2076,
	year          = 2001,
}

Contents (86 items)

7 ×#graph
7 ×#problem
6 ×#bound
6 ×#on the
5 ×#algorithm
4 ×#approximate
4 ×#automaton
4 ×#complexity
4 ×#multi
3 ×#combinator

ICALP-2001-Papadimitriou #algorithm #game studies #internet

Algorithms, Games, and the Internet (CHP), pp. 1–3.

ICALP-2001-Trakhtenbrot #automaton

Automata, Circuits, and Hybrids: Facets of Continuous Time (BAT), pp. 4–23.

ICALP-2001-Bouajjani #infinity #term rewriting #verification

Languages, Rewriting Systems, and Verification of Infinite-State Systems (AB), pp. 24–39.

ICALP-2001-Grosse-Rhode #modelling #object-oriented #semantics

Integrating Semantics for Object-Oriented System Models (MGR), pp. 40–60.

ICALP-2001-Nielsen #modelling #partial order #question #why

Modelling with Partial Orders — Why and Why Not? (MN), pp. 61–63.

ICALP-2001-Wegener #algorithm #aspect-oriented

Theoretical Aspects of Evolutionary Algorithms (IW), pp. 64–78.

ICALP-2001-Blaser #algebra #bound

Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical (MB), pp. 79–91.

ICALP-2001-BorosEGKM #generative #integer #linear #on the

On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities (EB, KME, VG, LK, KM), pp. 92–103.

ICALP-2001-Hesse

Division Is in Uniform TC0 (WH), pp. 104–114.

ICALP-2001-AgarwalAPV #framework

A Framework for Index Bulk Loading and Dynamization (PKA, LA, OP, JSV), pp. 115–127.

ICALP-2001-BilardiP #locality #memory management

A Characterization of Temporal Locality and Its Portability across Memory Hierarchies (GB, EP), pp. 128–139.

ICALP-2001-BrodalFPO #complexity #using

The Complexity of Constructing Evolutionary Trees Using Experiments (GSB, RF, CNSP, AÖ), pp. 140–151.

ICALP-2001-FlajoletGSV #statistics

Hidden Pattern Statistics (PF, YG, WS, BV), pp. 152–165.

ICALP-2001-SadakaneTT #algorithm #combinator #sequence

Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence (KS, NTC, TT), pp. 166–177.

ICALP-2001-Tiskin

All-Pairs Shortest Paths Computation in the BSP Model (AT), pp. 178–189.

ICALP-2001-ChazelleRT #approximate #sublinear

Approximating the Minimum Spanning Tree Weight in Sublinear Time (BC, RR, LT), pp. 190–200.

ICALP-2001-EngebretsenK #approximate #bound #metric

Approximation Hardness of TSP with Bounded Metrics (LE, MK), pp. 201–212.

ICALP-2001-FeigeL #source code

The RPR2 Rounding Technique for Semidefinite Programs (UF, ML), pp. 213–224.

ICALP-2001-GandhiKS #algorithm #approximate #problem

Approximation Algorithms for Partial Covering Problems (RG, SK, AS), pp. 225–236.

ICALP-2001-Seiden #on the #online #problem

On the Online Bin Packing Problem (SSS), pp. 237–248.

ICALP-2001-Thorup #graph

Quick k-Median, k-Center, and Facility Location for Sparse Graphs (MT), pp. 249–260.

ICALP-2001-AlberFN #complexity #exponential #graph #problem

Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems (JA, HF, RN), pp. 261–272.

ICALP-2001-CaiJ #algorithm

Subexponential Parameterized Algorithms Collapse the W-Hierarchy (LC, DWJ), pp. 273–284.

ICALP-2001-ChakrabartiK #bound #complexity #graph #random

Improved Lower Bounds on the Randomized Complexity of Graph Properties (AC, SK), pp. 285–296.

ICALP-2001-Dodis #random

New Imperfect Random Source with Applications to Coin-Flipping (YD), pp. 297–309.

ICALP-2001-FriedmanG #random #satisfiability

Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently (JF, AG), pp. 310–321.

ICALP-2001-Furer #linear #refinement

Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations (MF), pp. 322–333.

ICALP-2001-GoldreichVW #interactive #on the #proving

On Interactive Proofs with a Laconic Prover (OG, SPV, AW), pp. 334–345.

ICALP-2001-HoyerNS #order #quantum #sorting

Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness (PH, JN, YS), pp. 346–357.

ICALP-2001-SenV #bound #quantum

Lower Bounds in the Quantum Cell Probe Model (PS, SV), pp. 358–369.

ICALP-2001-BandiniS #axiom #bisimulation #probability

Axiomatizations for Probabilistic Bisimulation (EB, RS), pp. 370–381.

ICALP-2001-BoudolC #concurrent #source code

Noninterference for Concurrent Programs (GB, IC), pp. 382–395.

ICALP-2001-MadhusudanT #distributed #specification #synthesis

Distributed Controller Synthesis for Local Specifications (PM, PST), pp. 396–407.

ICALP-2001-SangiorgiV #automaton #distributed

A Distributed Abstract Machine for Safe Ambients (DS, AV), pp. 408–420.

ICALP-2001-BreugelW #probability #towards #verification

Towards Quantitative Verification of Probabilistic Transition Systems (FvB, JW), pp. 421–432.

ICALP-2001-LiN #generative #performance

Efficient Generation of Plane Triangulations without Repetitions (ZL, SIN), pp. 433–443.

ICALP-2001-LinCJW #problem #sequence

The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations (GHL, ZZC, TJ, JW), pp. 444–455.

ICALP-2001-ParkLC

Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher (SMP, JHL, KYC), pp. 456–468.

ICALP-2001-Roura

A New Method for Balancing Binary Search Trees (SR), pp. 469–480.

ICALP-2001-CormodeMS #editing #permutation

Permutation Editing and Matching via Embeddings (GC, SM, SCS), pp. 481–492.

ICALP-2001-CzumajS #testing

Testing Hypergraph Coloring (AC, CS), pp. 493–505.

ICALP-2001-IsobeZN #graph

Total Colorings of Degenerated Graphs (SI, XZ, TN), pp. 506–517.

ICALP-2001-MargaraS #decidability #graph #network

Decidable Properties of Graphs of All-Optical Networks (LM, JS), pp. 518–529.

ICALP-2001-MustafaP

Majority Consensus and the Local Majority Rule (NHM, AP), pp. 530–542.

ICALP-2001-DiekertM #commutative #decidability #equation

Solvability of Equations in Free Partially Commutative Groups Is Decidable (VD, AM), pp. 543–554.

ICALP-2001-DrosteZ

Rational Transformations of Formal Power Series (MD, GQZ), pp. 555–566.

ICALP-2001-FerencziHZ #combinator

Combinatorics of Three-Interval Exchanges (SF, CH, LQZ), pp. 567–578.

ICALP-2001-HarjuIKS #morphism

Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages (TH, OHI, JK, AS), pp. 579–590.

ICALP-2001-Kirsten #monad #problem #reduction

The Star Problem in Trace Monoids: Reductions Beyond C4 (DK), pp. 591–602.

ICALP-2001-Kunc #decidability #problem

The Trace Coding Problem Is Undecidable (MK), pp. 603–614.

ICALP-2001-RivalsR #combinator #string

Combinatorics of Periods in Strings (ER, SR), pp. 615–626.

ICALP-2001-ShankarKSR

Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct (PS, PNAK, HS, BSR), pp. 627–638.

ICALP-2001-AbdullaBB #effectiveness #queue

Effective Lossy Queue Languages (PAA, LB, AB), pp. 639–651.

ICALP-2001-BenediktGR #model checking #state machine #strict

Model Checking of Unrestricted Hierarchical State Machines (MB, PG, TWR), pp. 652–666.

ICALP-2001-Boreale #analysis #encryption #protocol

Symbolic Trace Analysis of Cryptographic Protocols (MB), pp. 667–681.

ICALP-2001-ComonCM #automaton #constraints #memory management #protocol #set

Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols (HC, VC, JM), pp. 682–693.

ICALP-2001-EtessamiWS #automaton #game studies #reduction #simulation

Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata (KE, TW, RAS), pp. 694–707.

ICALP-2001-GottlobP #clique #model checking

Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width (GG, RP), pp. 708–719.

ICALP-2001-MuschollP #communication #finite #protocol #sequence chart

From Finite State Communication Protocols to High-Level Message Sequence Charts (AM, DP), pp. 720–731.

ICALP-2001-CaragiannisFKPR #network

Fractional Path Coloring with Applications to WDM Networks (IC, AF, CK, SP, HR), pp. 732–743.

ICALP-2001-CohenHK #aspect-oriented #consistency #distributed #performance #using

Performance Aspects of Distributed Caches Using TTL-Based Consistency (EC, EH, HK), pp. 744–756.

ICALP-2001-FraigniaudG

Routing in Trees (PF, CG), pp. 757–772.

ICALP-2001-Havill #array #linear #online

Online Packet Routing on Linear Arrays and Rings (JTH), pp. 773–784.

ICALP-2001-Sibeyn #performance

Faster Gossiping on Butterflies (JFS), pp. 785–796.

ICALP-2001-AlurEY #graph #verification

Realizability and Verification of MSC Graphs (RA, KE, MY), pp. 797–808.

ICALP-2001-Madhusudan #behaviour #branch #graph #reasoning #sequence

Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs (PM), pp. 809–820.

ICALP-2001-Maier #framework #reasoning

A Set-Theoretic Framework for Assume-Guarantee Reasoning (PM), pp. 821–834.

ICALP-2001-ViswanathanV #composition #reasoning

Foundations for Circular Compositional Reasoning (MV, RV), pp. 835–847.

ICALP-2001-ChekuriK

A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines (CC, SK), pp. 848–861.

ICALP-2001-ChrobakCINSW #multi #problem #scheduling

The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts (MC, JC, CI, JN, JS, GJW), pp. 862–874.

ICALP-2001-FishkinJP #multi #on the

On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates (AVF, KJ, LP), pp. 875–886.

ICALP-2001-Woeginger #constraints #on the #precedence #scheduling

On the Approximability of Average Completion Time Scheduling under Precedence Constraints (GJW), pp. 887–897.

ICALP-2001-Baum-Waidner #contract #multi

Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds (BBW), pp. 898–911.

ICALP-2001-BeimelI #information retrieval

Information-Theoretic Private Information Retrieval: A Unified Construction (AB, YI), pp. 912–926.

ICALP-2001-FeigenbaumIMNSW #approximate #multi

Secure Multiparty Computation of Approximations (JF, YI, TM, KN, MS, RNW), pp. 927–938.

ICALP-2001-KiayiasY #game studies #polynomial

Secure Games with Polynomial Expressions (AK, MY), pp. 939–950.

ICALP-2001-BofillG #on the

On the Completeness of Arbitrary Selection Strategies for Paramodulation (MB, GG), pp. 951–962.

ICALP-2001-HonsellMS #algebra #approach #axiom

An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS (FH, MM, IS), pp. 963–978.

ICALP-2001-KorovinV #constraints #theorem proving

Knuth-Bendix Constraint Solving Is NP-Complete (KK, AV), pp. 979–992.

ICALP-2001-SchroderMT

Amalgamation in CASL via Enriched Signatures (LS, TM, AT), pp. 993–1004.

ICALP-2001-AtseriasBE #bound

Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution (AA, MLB, JLE), pp. 1005–1016.

ICALP-2001-BuhrmanTV #bound #simulation

Time and Space Bounds for Reversible Simulation (HB, JT, PMBV), pp. 1017–1027.

ICALP-2001-DaiLLM #finite

Finite-State Dimension (JJD, JIL, JHL, EM), pp. 1028–1039.

ICALP-2001-HemaspaandraKW #complexity

The Complexity of Computing the Size of an Interval (LAH, SK, KWW), pp. 1040–1051.

ICALP-2001-JurdzinskiK #communication #finite #memory management

Communication Gap for Finite Memory Devices (TJ, MK), pp. 1052–1064.

ICALP-2001-Servedio #learning #quantum

Separating Quantum and Classical Learning (RAS), pp. 1065–1080.