default search action
30th ICALP 2003: Eindhoven, The Netherlands
- Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger:
Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings. Lecture Notes in Computer Science 2719, Springer 2003, ISBN 3-540-40493-7
Invited Lectures
- Jan A. Bergstra, Inge Bethke:
Polarized Process Algebra and Program Equivalence. 1-21 - Anne Condon:
Problems on RNA Secondary Structure Prediction and Design. 22-32 - Amos Fiat:
Some Issues Regarding Search, Censorship, and Anonymity in Peer to Peer Networks. 33 - Petra Mutzel
:
The SPQR-Tree Data Structure in Graph Drawing. 34-46 - Doron A. Peled:
Model Checking and Testing Combined. 47-63 - Moshe Y. Vardi:
Logic and Automata: A Match Made in Heaven. 64-65
Algorithms
- Juraj Hromkovic, Georg Schnitger:
Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes. 66-80 - Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro:
Generalized Framework for Selectors with Applications in Optimal Group Testing. 81-96 - Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung:
Decoding of Interleaved Reed Solomon Codes over Noisy Data. 97-108
Process Algebra
- Stefan Blom, Wan J. Fokkink, Sumit Nain:
On the Axiomatizability of Ready Traces, Ready Simulation, and Failure Traces. 109-118 - Daniele Gorla
Resource Access and Mobility Control with Dynamic Privileges Acquisition. 119-132 - Nadia Busi, Maurizio Gabbrielli
Replication vs. Recursive Definitions in Channel Based Calculi. 133-144
Approximation Algorithms
- Alexander A. Ageev, Yinyu Ye, Jiawei Zhang:
Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem. 145-156 - Markus Bläser:
An Improved Approximation Algorithm for the Asymmetric TSP with Strengthened Triangle Inequality. 157-163 - Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan:
An Improved Approximation Algorithm for Vertex Cover with Hard Capacities. 164-175 - Sanjeev Arora, Kevin L. Chang:
Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem. 176-188 - Chandra Chekuri, Sudipto Guha, Joseph Naor:
Approximating Steiner k-Cuts. 189-199 - Amin Coja-Oghlan, Cristopher Moore
MAX k-CUT and Approximating the Chromatic Number of Random Graphs. 200-211 - Michael Elkin, Guy Kortsarz:
Approximation Algorithm for Directed Telephone Multicast Problem. 212-223
Languages and Programming
- Davide Ancona, Sonia Fagorzi, Eugenio Moggi, Elena Zucca:
Mixin Modules and Computational Effects. 224-238 - Alexander Okhotin:
Decision Problems for Language Equations with Boolean Operations. 239-251 - Roberto Bruni, José Meseguer:
Generalized Rewrite Theories. 252-266
Complexity
- Luis Antunes, Lance Fortnow:
Sophistication Revisited. 267-277 - John M. Hitchcock
Scaled Dimension and Nonuniform Complexity. 278-290 - Peter Høyer, Michele Mosca, Ronald de Wolf:
Quantum Search on Bounded-Error Inputs. 291-299 - Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen:
A Direct Sum Theorem in Communication Complexity via Message Compression. 300-315
Data Structures
- Gianni Franceschini, Roberto Grossi:
Optimal Cache-Oblivious Implicit Dictionaries. 316-331 - Anna Gál, Peter Bro Miltersen:
The Cell Probe Complexity of Succinct Data Structures. 332-344 - J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao
Succinct Representations of Permutations. 345-356 - Rajeev Raman
Succinct Dynamic Dictionaries and Trees. 357-368
Graph Algorithms
- Amos Korman, David Peleg:
Labeling Schemes for Weighted Dynamic Trees. 369-383 - Surender Baswana, Sandeep Sen:
A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n1+1/k) Size in Weighted Graphs. 384-296 - Alexander Hall, Steffen Hippler, Martin Skutella:
Multicommodity Flows over Time: Efficient Algorithms and Complexity. 397-409 - Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd:
Multicommodity Demand Flow in a Tree. 410-425
Automata
- Manfred Droste, Dietrich Kuske:
Skew and Infinitary Formal Power Series. 426-438 - Juraj Hromkovic, Georg Schnitger:
Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation. 439-451 - François Denis, Yann Esposito:
Residual Languages and Probabilistic Automata. 452-463 - Mariëlle Stoelinga, Frits W. Vaandrager:
A Testing Scenario for Probabilistic Automata. 464-477 - Géraud Sénizergues:
The Equivalence Problem for t-Turn DPDA Is Co-NP. 478-489 - Markus Holzer
Flip-Pushdown Automata: k+1 Pushdown Reversals Are Better than k. 490-501
Optimization and Games
- Eyal Even-Dar, Alexander Kesselman, Yishay Mansour:
Convergence Time to Nash Equilibria. 502-513 - Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien, Manuel Rode:
Nashification and the Coordination Ratio for a Selfish Routing Game. 514-526 - Vipul Bansal, Aseem Agrawal, Varun S. Malhotra:
Stable Marriages with Multiple Partners: Efficient Search for an Optimal Solution. 527-542 - Endre Boros, Khaled M. Elbassioni
An Intersection Inequality for Discrete Distributions and Related Generation Problems. 543-555
Graphs and Bisimulation
- Thierry Cachat:
Higher Order Pushdown Automata, the Caucal Hierarchy of Graphs and Parity Games. 556-569 - Richard Mayr:
Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes. 570-583 - Massimo Merro, Francesco Zappa Nardelli:
Bisimulation Proof Methods for Mobile Ambients. 584-598 - Arnaud Carayol, Thomas Colcombet:
On Equivalent Representations of Infinite Structures. 599-610
Online Problems
- Arnold Schönhage:
Adaptive Raising Strategies Optimizing Relative Efficiency. 611-623 - René Sitters, Leen Stougie, Willem de Paepe:
A Competitive Algorithm for the General 2-Server Problem. 624-636 - Dimitris Fotakis
On the Competitive Ratio for Online Facility Location. 637-652 - Susanne Albers, Rob van Stee:
A Study of Integrated Document and Connection Caching. 653-667
Verification
- Gaoyan Xie, Zhe Dang, Oscar H. Ibarra:
A Solvable Class of Quadratic Diophantine Equations with Applications to Verification of Infinite-State Systems. 668-680 - Felix Klaedtke, Harald Rueß:
Monadic Second-Order Logics with Cardinalities. 681-696 - Orna Kupferman, Moshe Y. Vardi:
Π2 ∩ Σ2 ≡ AFMC. 697-713 - Tatiana Rybina, Andrei Voronkov:
Upper Bounds for a Theory of Queues. 714-724
Around the Internet
- Noam Berger, Béla Bollobás, Christian Borgs
Degree Distribution of the FKP Network Model. 725-738 - Vincent D. Blondel, Paul Van Dooren:
Similarity Matrices for Pairs of Graphs. 739-750 - Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor:
Algorithmic Aspects of Bandwidth Trading. 751-766
Temporal Logic and Model Checking
- Jan Johannsen, Martin Lange:
CTL+ Is Complete for Double Exponential Time. 767-775 - Salvatore La Torre, Margherita Napoli, Mimmo Parente, Gennaro Parlato:
Hierarchical and Recursive State Machines with Context-Dependent Properties. 776-789 - Philippe Schnoebelen:
Oracle Circuits for Branching-Time Model Checking. 790-801
Graph Problems
- Luisa Gargano
There Are Spanning Spiders in Dense Graphs (and We Know How to Find Them). 802-816 - Jirí Fiala, Daniël Paulusma:
The Computational Complexity of the Role Assignment Problem. 817-828 - Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs. 829-844 - Jianer Chen, Iyad A. Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge Xia:
Genus Characterizes the Complexity of Graph Problems: Some Tight Results. 845-856
Logic and Lambda-Calculus
- Cindy Eisner, Dana Fisman
The Definition of a Temporal Clock Operator. 857-870 - Zena M. Ariola, Hugo Herbelin:
Minimal Classical Logic and Control Operators. 871-885 - Thomas A. Henzinger, Ranjit Jhala, Rupak Majumdar:
Counterexample-Guided Control. 886-902 - Jo Erskine Hannay:
Axiomatic Criteria for Quotients and Subobjects for Higher-Order Data Types. 903-917
Data Structures and Algorithms
- Yossi Matias, Ely Porat:
Efficient Pebbling for List Traversal Synopses. 918-928 - Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat:
Function Matching: Algorithms, Applications, and a Lower Bound. 929-942 - Juha Kärkkäinen, Peter Sanders:
Simple Linear Work Suffix Array Construction. 943-955
Types and Categories
- Francisco Gutiérrez, Blas C. Ruiz:
Expansion Postponement via Cut Elimination in Sequent Calculi for Pure Type Systems. 956-968 - Michele Bugliesi
Secrecy in Untrusted Networks. 969-983 - Arkadev Chattopadhyay, Denis Thérien:
Locally Commutative Categories. 984-995
Probabilistic Systems
- Ernst-Erich Doberkat:
Semi-pullbacks and Bisimulations in Categories of Stochastic Relations. 996-1007 - Alexander Moshe Rabinovich:
Quantitative Analysis of Probabilistic Lossy Channel Systems. 1008-1021 - Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar:
Discounting the Future in Systems Theory. 1022-1037 - Luca de Alfaro, Marco Faella:
Information Flow in Concurrent Games. 1038-1053
Sampling and Randomness
- Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, Masafumi Yamashita:
Impact of Local Topological Information on Random Walks on Finite Graphs. 1054-1067 - Jens Jägersküpper:
Analysis of a Simple Evolutionary Algorithm for Minimization in Euclidean Spaces. 1068-1079 - Dominique Poulalhon, Gilles Schaeffer:
Optimal Coding and Sampling of Triangulations. 1080-1094 - Manuel Bodirsky
Generating Labeled Planar Graphs Uniformly at Random. 1095-1107
Scheduling
- Pierluigi Crescenzi
Online Load Balancing Made Simple: Greedy Strikes Back. 1108-1122 - Joseph Naor, Hadas Shachnai, Tami Tamir:
Real-Time Scheduling with a Budget. 1123-1137 - Brian C. Dean, Michel X. Goemans:
Improved Approximation Algorithms for Minimum-Space Advertisement Scheduling. 1138-1152 - Baruch Awerbuch, André Brinkmann, Christian Scheideler:
Anycasting in Adversarial Systems: Routing and Admission Control. 1153-1168
Geometric Problems
- Sergei Bespamyatnikh, Michael Segal
Dynamic Algorithms for Approximating Interdistances. 1169-1180 - Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe
Solving the Robots Gathering Problem. 1181-1196
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-13 19:00 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: