29. ICALP 2002: Málaga, Spain

Peter Widmayer, Francisco Triguero Ruiz, Rafael Morales Bueno, Matthew Hennessy, Stephan Eidenbenz, Ricardo Conejo (Eds.): Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings. Lecture Notes in Computer Science 2380 Springer 2002, ISBN 3-540-43864-5 BibTeX

@proceedings{DBLP:conf/icalp/2002,
  editor    = {Peter Widmayer and
               Francisco Triguero Ruiz and
               Rafael Morales Bueno and
               Matthew Hennessy and
               Stephan Eidenbenz and
               Ricardo Conejo},
  title     = {Automata, Languages and Programming, 29th International Colloquium,
               ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings},
  booktitle = {ICALP},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {2380},
  year      = {2002},
  isbn      = {3-540-43864-5},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talks

John H. Reif:
Molecular Assembly and Computation: From Theory to Experimental Demonstrations. 1-21
Electronic Edition (Springer LINK) BibTeX
Madhav V. Marathe:
Towards a Predictive Computational Complexity Theory. 22-31
Electronic Edition (Springer LINK) BibTeX
Andrew M. Pitts:
Equivariant Syntax and Semantics. 32-36
Electronic Edition (Springer LINK) BibTeX
Géraud Sénizergues:
L(A) = L(B)? Decidability Results from Complete Formal Systems. 37
Electronic Edition (Springer LINK) BibTeX
Alberto Del Lungo, Andrea Frosini, Maurice Nivat, Laurent Vuillon:
Discrete Tomography: Reconstruction under Periodicity Constraints. 38-56
Electronic Edition (Springer LINK) BibTeX
Heikki Mannila:
Local and Global Methods in Data Mining: Basic Techniques and Open Problems. 57-68
Electronic Edition (Springer LINK) BibTeX
Manuel V. Hermenegildo, Germán Puebla, Francisco Bueno, Pedro López-García:
Program Debugging and Validation Using Semantic Approximations and Partial Specifications. 69-72
Electronic Edition (Springer LINK) BibTeX

Best Papers

Lars Engebretsen, Jonas Holmerin, Alexander Russell:
Inapproximability Results for Equations over Finite Groups. 73-84
Electronic Edition (Springer LINK) BibTeX
Seth Pettie:
A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs. 85-97
Electronic Edition (Springer LINK) BibTeX
Thomas Colcombet:
On Families of Graphs Having a Decidable First Order Theory with Reachability. 98-109
Electronic Edition (Springer LINK) BibTeX

Contributions

Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou:
Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. 110-122
Electronic Edition (Springer LINK) BibTeX
Dimitris Fotakis, Spyros C. Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul G. Spirakis:
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. 123-134
Electronic Edition (Springer LINK) BibTeX
Sanjeev Khanna, Joseph Naor, Danny Raz:
Control Message Aggregation in Group Communication Protocols. 135-146
Electronic Edition (Springer LINK) BibTeX
Tomasz Jurdzinski, Krzysztof Lorys:
Church-Rosser Languages vs. UCFL. 147-158
Electronic Edition (Springer LINK) BibTeX
Sebastian Bala:
Intersection of Regular Languages and Star Hierarchy. 159-169
Electronic Edition (Springer LINK) BibTeX
Sylvain Lombardy:
On the Construction of Reversible Automata for Reversible Languages. 170-182
Electronic Edition (Springer LINK) BibTeX
Amr Elmasry:
Priority Queues, Pairing, and Adaptive Sorting. 183-194
Electronic Edition (Springer LINK) BibTeX
Michael A. Bender, Richard Cole, Rajeev Raman:
Exponential Structures for Efficient Cache-Oblivious Algorithms. 195-207
Electronic Edition (Springer LINK) BibTeX
Russell Impagliazzo, Nathan Segerlind:
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. 208-219
Electronic Edition (Springer LINK) BibTeX
Juan Luis Esteban, Nicola Galesi, Jochen Messner:
On the Complexity of Resolution with Bounded Conjunctions. 220-231
Electronic Edition (Springer LINK) BibTeX
Aggelos Kiayias, Moti Yung:
Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes. 232-243
Electronic Edition (Springer LINK) BibTeX
Yuval Ishai, Eyal Kushilevitz:
Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials. 244-256
Electronic Edition (Springer LINK) BibTeX
Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik:
Exponential Lower Bound for Static Semi-algebraic Proofs. 257-268
Electronic Edition (Springer LINK) BibTeX
Andreas Jakoby, Maciej Liskiewicz:
Paths Problems in Symmetric Logarithmic Space. 269-280
Electronic Edition (Springer LINK) BibTeX
Peter Damaschke:
Scheduling Search Procedures. 281-292
Electronic Edition (Springer LINK) BibTeX
Kazuo Iwama, Shiro Taketomi:
Removable Online Knapsack Problems. 293-305
Electronic Edition (Springer LINK) BibTeX
Leah Epstein, Steven S. Seiden, Rob van Stee:
New Bounds for Variable-Sized and Resource Augmented Online Bin Packing. 306-317
Electronic Edition (Springer LINK) BibTeX
Nicolas Ollinger:
The Quest for Small Universal Cellular Automata. 318-329
Electronic Edition (Springer LINK) BibTeX
Christophe Papazian, Eric Rémila:
Hyperbolic Recognition by Graph Automata. 330-342
Electronic Edition (Springer LINK) BibTeX
Farid M. Ablayev, Cristopher Moore, Chris Pollett:
Quantum and Stochastic Branching Programs of Bounded Width. 343-354
Electronic Edition (Springer LINK) BibTeX
Luisa Gargano, Pavol Hell, Ladislav Stacho, Ugo Vaccaro:
Spanning Trees with Bounded Number of Branch Vertices. 355-365
Electronic Edition (Springer LINK) BibTeX
René Beier, Peter Sanders, Naveen Sivadasan:
Energy Optimal Routing in Radio Networks Using Geometric Data Structures. 366-376
Electronic Edition (Springer LINK) BibTeX
Malin Christersson, Leszek Gasieniec, Andrzej Lingas:
Gossiping with Bounded Size Messages in ad hoc Radio Networks. 377-389
Electronic Edition (Springer LINK) BibTeX
Wolfgang Merkle:
The Kolmogorov-Loveland Stochastic Sequences Are Not Closed under Selecting Subsequences. 390-400
Electronic Edition (Springer LINK) BibTeX
Robert A. Hearn, Erik D. Demaine:
The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications. 401-413
Electronic Edition (Springer LINK) BibTeX
Víctor Dalmau:
Constraint Satisfaction Problems in Non-deterministic Logarithmic Space. 414-425
Electronic Edition (Springer LINK) BibTeX
Gerth Stølting Brodal, Rolf Fagerberg:
Cache Oblivious Distribution Sweeping. 426-438
Electronic Edition (Springer LINK) BibTeX
Anna Östlin, Rasmus Pagh:
One-Probe Search. 439-450
Electronic Edition (Springer LINK) BibTeX
Moses Charikar, Piotr Indyk, Rina Panigrahy:
New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems. 451-462
Electronic Edition (Springer LINK) BibTeX
Keye Martin, Michael W. Mislove, James Worrell:
Measuring the Probabilistic Powerdomain. 463-475
Electronic Edition (Springer LINK) BibTeX
C.-H. Luke Ong, Pietro Di Gianantonio:
Games Characterizing Levy-Longo Trees. 476-487
Electronic Edition (Springer LINK) BibTeX
Andrej Bauer, Martín Hötzel Escardó, Alex K. Simpson:
Comparing Functional Paradigms for Exact Real-Number Computation. 488-500
Electronic Edition (Springer LINK) BibTeX
Philippe Duchon, Philippe Flajolet, Guy Louchard, Gilles Schaeffer:
Random Sampling from Boltzmann Principles. 501-513
Electronic Edition (Springer LINK) BibTeX
Amalia Duch, Conrado Martínez:
On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures. 514-524
Electronic Edition (Springer LINK) BibTeX
Marco Kick:
Bialgebraic Modelling of Timed Processes. 525-536
Electronic Edition (Springer LINK) BibTeX
Franck van Breugel, Steven Shalit, James Worrell:
Testing Labelled Markov Processes. 537-548
Electronic Edition (Springer LINK) BibTeX
John M. Hitchcock, Jack H. Lutz:
Why Computational Complexity Requires Stricter Martingales. 549-560
Electronic Edition (Springer LINK) BibTeX
John M. Hitchcock:
Correspondence Principles for Effective Dimensions. 561-571
Electronic Edition (Springer LINK) BibTeX
José Meseguer, Grigore Rosu:
A Total Approach to Partial Algebraic Specification. 572-584
Electronic Edition (Springer LINK) BibTeX
Markus Lohrey, Pedro R. D'Argenio, Holger Hermanns:
Axiomatising Divergence. 585-596
Electronic Edition (Springer LINK) BibTeX
Luca Cardelli, Philippa Gardner, Giorgio Ghelli:
A Spatial Logic for Querying Graphs. 597-610
Electronic Edition (Springer LINK) BibTeX
Tomasz Radzik:
Improving Time Bounds on Maximum Generalised Flow Computations by Contracting the Network. 611-622
Electronic Edition (Springer LINK) BibTeX
Piotr Berman, Marek Karpinski:
Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. 623-632
Electronic Edition (Springer LINK) BibTeX
Camil Demetrescu, Giuseppe F. Italiano:
Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths. 633-643
Electronic Edition (Springer LINK) BibTeX
Thomas A. Henzinger, Sriram C. Krishnan, Orna Kupferman, Freddy Y. C. Mang:
Synthesis of Uninitialized Systems. 644-656
Electronic Edition (Springer LINK) BibTeX
Blaise Genest, Anca Muscholl, Helmut Seidl, Marc Zeitoun:
Infinite-State High-Level MSCs: Model-Checking and Realizability. 657-668
Electronic Edition (Springer LINK) BibTeX
Klaus Wich:
Universal Inherence of Cycle-Free Context-Free Ambiguity Functions. 669-680
Electronic Edition (Springer LINK) BibTeX
Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss:
Histogramming Data Streams with Fast Per-Item Processing. 681-692
Electronic Edition (Springer LINK) BibTeX
Moses Charikar, Kevin Chen, Martin Farach-Colton:
Finding Frequent Items in Data Streams. 693-703
Electronic Edition (Springer LINK) BibTeX
Thierry Cachat:
Symbolic Strategy Synthesis for Games on Pushdown Graphs. 704-715
Electronic Edition (Springer LINK) BibTeX
Jirí Srba:
Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard. 716-727
Electronic Edition (Springer LINK) BibTeX
Gerth Stølting Brodal, Rune B. Lyngsø, Anna Östlin, Christian N. S. Pedersen:
Solving the String Statistics Problem in Time O(n log n). 728-739
Electronic Edition (Springer LINK) BibTeX
Xiaotie Deng, Guojun Li, Zimao Li, Bin Ma, Lusheng Wang:
A PTAS for Distinguishing (Sub)string Selection. 740-751
Electronic Edition (Springer LINK) BibTeX
Dietrich Kuske, Markus Lohrey:
On the Theory of One-Step Rewriting in Trace Monoids. 752-763
Electronic Edition (Springer LINK) BibTeX
Michal Bielecki, Jan Hidders, Jan Paredaens, Jerzy Tyszkiewicz, Jan Van den Bussche:
Navigating with a Browser. 764-775
Electronic Edition (Springer LINK) BibTeX
V. S. Anil Kumar, Madhav V. Marathe:
Improved Results for Stackelberg Scheduling Strategies. 776-787
Electronic Edition (Springer LINK) BibTeX
Udo Adamy, Christoph Ambühl, R. Sai Anand, Thomas Erlebach:
Call Control in Rings. 788-799
Electronic Edition (Springer LINK) BibTeX
Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania:
Preemptive Scheduling in Overloaded Systems. 800-811
Electronic Edition (Springer LINK) BibTeX
Juhani Karhumäki, Leonid P. Lisovik:
The Equivalence Problem of Finite Substitutions on ab^*c, with Applications. 812-820
Electronic Edition (Springer LINK) BibTeX
Colin Stirling:
Deciding DPDA Equivalence Is Primitive Recursive. 821-832
Electronic Edition (Springer LINK) BibTeX
Mikolaj Bojanczyk:
Two-Way Alternating Automata and Finite Models. 833-844
Electronic Edition (Springer LINK) BibTeX
Piotr Berman, Marek Karpinski, Yakov Nekrich:
Approximating Huffman Codes in Parallel. 845-855
Electronic Edition (Springer LINK) BibTeX
Carlo Fantozzi, Andrea Pietracaprina, Geppino Pucci:
Seamless Integration of Parallelism and Memory Hierarchy. 856-867
Electronic Edition (Springer LINK) BibTeX
Noam Nisan:
The Communication Complexity of Approximate Set Packing and Covering. 868-875
Electronic Edition (Springer LINK) BibTeX
Benjamin Doerr:
Antirandomizing the Wrong Game. 876-887
Electronic Edition (Springer LINK) BibTeX
Karhan Akcoglu, Petros Drineas, Ming-Yang Kao:
Fast Universalization of Investment Strategies with Provably Good Relative Returns. 888-900
Electronic Edition (Springer LINK) BibTeX
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking:
Randomized Pursuit-Evasion in Graphs. 901-912
Electronic Edition (Springer LINK) BibTeX
J. B. Wells:
The Essence of Principal Typings. 913-925
Electronic Edition (Springer LINK) BibTeX
Bharat Adsul, Milind A. Sohoni:
Complete and Tractable Local Linear Time Temporal Logics over Traces. 926-937
Electronic Edition (Springer LINK) BibTeX
Paul Gastin, Madhavan Mukund:
An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces. 938-949
Electronic Edition (Springer LINK) BibTeX
Vasco Brattka:
Random Numbers and an Incomplete Immune Recursive Set. 950-961
Electronic Edition (Springer LINK) BibTeX
Peter Hertling:
A Banach-Mazur Computable But Not Markov Computable Function on the Computable Real Numbers. 962-972
Electronic Edition (Springer LINK) BibTeX
Artur Czumaj, Andrzej Lingas, Hairong Zhao:
Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem. 973-984
Electronic Edition (Springer LINK) BibTeX
Andreas Björklund, Thore Husfeldt:
Finding a Path of Superlogarithmic Length. 985-992
Electronic Edition (Springer LINK) BibTeX
Ryuhei Uehara:
Linear Time Algorithms on Chordal Bipartite and Strongly Chordal Graphs. 993-1004
Electronic Edition (Springer LINK) BibTeX
Jonas Holmerin:
Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs. 1005-1016
Electronic Edition (Springer LINK) BibTeX
Yoshiharu Kohayakawa, Brendan Nagle, Vojtech Rödl:
Efficient Testing of Hypergraphs. 1017-1028
Electronic Edition (Springer LINK) BibTeX
Xiaodong Wu, Danny Z. Chen:
Optimal Net Surface Problems with Applications. 1029-1042
Electronic Edition (Springer LINK) BibTeX
Nicolas Bonichon, Bertrand Le Saëc, Mohamed Mosbah:
Wagner's Theorem on Realizers. 1043-1053
Electronic Edition (Springer LINK) BibTeX
Vincenzo Liberatore:
Circular Arrangements. 1054-1066
Electronic Edition (Springer LINK) BibTeX