default search action
28th ICALP 2001: Heraklion, Crete, Greece
- Fernando Orejas, Paul G. Spirakis, Jan van Leeuwen:
Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings. Lecture Notes in Computer Science 2076, Springer 2001, ISBN 3-540-42287-0
Keynote Papers
- Christos H. Papadimitriou:
Algorithms, Games, and the Internet. 1-3 - Boris A. Trakhtenbrot:
Automata, Circuits, and Hybrids: Facets of Continuous Time. 4-23
Invited Papers
- Ahmed Bouajjani:
Languages, Rewriting Systems, and Verification of Infinite-State Systems. 24-39 - Martin Große-Rhode:
Integrating Semantics for Object-Oriented System Models. 40-60 - Mogens Nielsen:
Modelling with Partial Orders - Why and Why Not? 61-63 - Ingo Wegener:
Theoretical Aspects of Evolutionary Algorithms. 64-78
Algebraic and Circuit Complexity
- Markus Bläser:
Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical. 79-91 - Endre Boros, Khaled M. Elbassioni
, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities. 92-103 - William Hesse:
Division Is in Uniform TC0. 104-114
Algorithm Analysis
- Pankaj K. Agarwal, Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter:
A Framework for Index Bulk Loading and Dynamization. 115-127 - Gianfranco Bilardi, Enoch Peserico:
A Characterization of Temporal Locality and Its Portability across Memory Hierarchies. 128-139 - Gerth Stølting Brodal
The Complexity of Constructing Evolutionary Trees Using Experiments. 140-151 - Philippe Flajolet, Yves Guivarc'h, Wojciech Szpankowski, Brigitte Vallée:
Hidden Pattern Statistics. 152-165 - Kunihiko Sadakane
Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence. 166-177 - Alexandre Tiskin
All-Pairs Shortest Paths Computation in the BSP Model. 178-189
Approximation and Optimization
- Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan:
Approximating the Minimum Spanning Tree Weight in Sublinear Time. 190-200 - Lars Engebretsen, Marek Karpinski:
Approximation Hardness of TSP with Bounded Metrics. 201-212 - Uriel Feige, Michael Langberg:
The RPR2 Rounding Technique for Semidefinite Programs. 213-224 - Rajiv Gandhi, Samir Khuller, Aravind Srinivasan
Approximation Algorithms for Partial Covering Problems. 225-236 - Steven S. Seiden:
On the Online Bin Packing Problem. 237-248 - Mikkel Thorup:
Quick k-Median, k-Center, and Facility Location for Sparse Graphs. 249-260
Complexity
- Jochen Alber, Henning Fernau
Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems. 261-272 - Liming Cai, David W. Juedes
Subexponential Parameterized Algorithms Collapse the W-Hierarchy. 273-284 - Amit Chakrabarti, Subhash Khot:
Improved Lower Bounds on the Randomized Complexity of Graph Properties. 285-296 - Yevgeniy Dodis:
New Imperfect Random Source with Applications to Coin-Flipping. 297-309 - Joel Friedman
Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently. 310-321 - Martin Fürer
Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations. 322-333 - Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
On Interactive Proofs with a Laconic Prover. 334-345 - Peter Høyer, Jan Neerbek, Yaoyun Shi:
Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness. 346-357 - Pranab Sen, Srinivasan Venkatesh:
Lower Bounds in the Quantum Cell Probe Model. 358-369
Concurrency
- Emanuele Bandini, Roberto Segala:
Axiomatizations for Probabilistic Bisimulation. 370-381 - Gérard Boudol, Ilaria Castellani:
Noninterference for Concurrent Programs. 382-395 - P. Madhusudan, P. S. Thiagarajan:
Distributed Controller Synthesis for Local Specifications. 396-407 - Davide Sangiorgi, Andrea Valente
A Distributed Abstract Machine for Safe Ambients. 408-420 - Franck van Breugel, James Worrell:
Towards Quantitative Verification of Probabilistic Transition Systems. 421-432
Efficient Datastructures
- Zhangjian Li, Shin-Ichi Nakano:
Efficient Generation of Plane Triangulations without Repetitions. 433-443 - Guo-Hui Lin, Zhi-Zhong Chen, Tao Jiang, Jianjun Wen:
The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations. 444-455 - Sang-Min Park, Jae-Ha Lee, Kyung-Yong Chwa:
Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher. 456-468 - Salvador Roura:
A New Method for Balancing Binary Search Trees. 469-480
Graph Algorithms
- Graham Cormode
Permutation Editing and Matching via Embeddings. 481-492 - Artur Czumaj, Christian Sohler:
Testing Hypergraph Coloring. 493-505 - Shuji Isobe, Xiao Zhou, Takao Nishizeki:
Total Colorings of Degenerated Graphs. 506-517 - Luciano Margara
Decidable Properties of Graphs of All-Optical Networks. 518-529 - Nabil H. Mustafa, Aleksandar Pekec:
Majority Consensus and the Local Majority Rule. 530-542
Language Theory, Codes, and Automata
- Volker Diekert, Anca Muscholl:
Solvability of Equations in Free Partially Commutative Groups Is Decidable. 543-554 - Manfred Droste, Guo-Qiang Zhang:
Rational Transformations of Formal Power Series. 555-566 - Sébastien Ferenczi, Charles Holton, Luca Q. Zamboni:
Combinatorics of Three-Interval Exchanges. 567-578 - Tero Harju, Oscar H. Ibarra, Juhani Karhumäki, Arto Salomaa:
Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages. 579-590 - Daniel Kirsten:
The Star Problem in Trace Monoids: Reductions Beyond C4. 591-602 - Michal Kunc:
The Trace Coding Problem Is Undecidable. 603-614 - Eric Rivals, Sven Rahmann:
Combinatorics of Periods in Strings. 615-626 - Priti Shankar, P. N. A. Kumar, Harmeet Singh, B. Sundar Rajan:
Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct. 627-638
Model Checking and Protocol Analysis
- Parosh Aziz Abdulla, Luc Boasson, Ahmed Bouajjani:
Effective Lossy Queue Languages. 639-651 - Michael Benedikt, Patrice Godefroid, Thomas W. Reps:
Model Checking of Unrestricted Hierarchical State Machines. 652-666 - Michele Boreale:
Symbolic Trace Analysis of Cryptographic Protocols. 667-681 - Hubert Comon, Véronique Cortier, John Mitchell:
Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols. 682-693 - Kousha Etessami, Thomas Wilke, Rebecca A. Schuller:
Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata. 694-707 - Georg Gottlob, Reinhard Pichler:
Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width. 708-719 - Anca Muscholl, Doron A. Peled:
From Finite State Communication Protocols to High-Level Message Sequence Charts. 720-731
Networks and Routing
- Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes, Hervé Rivano:
Fractional Path Coloring with Applications to WDM Networks. 732-743 - Edith Cohen, Eran Halperin, Haim Kaplan:
Performance Aspects of Distributed Caches Using TTL-Based Consistency. 744-756 - Pierre Fraigniaud, Cyril Gavoille:
Routing in Trees. 757-772 - Jessen T. Havill:
Online Packet Routing on Linear Arrays and Rings. 773-784 - Jop F. Sibeyn:
Faster Gossiping on Butterflies. 785-796
Reasoning and Verification
- Rajeev Alur, Kousha Etessami, Mihalis Yannakakis:
Realizability and Verification of MSC Graphs. 797-808 - P. Madhusudan:
Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs. 809-820 - Patrick Maier:
A Set-Theoretic Framework for Assume-Guarantee Reasoning. 821-834 - Mahesh Viswanathan, Ramesh Viswanathan:
Foundations for Circular Compositional Reasoning. 835-847
Scheduling
- Chandra Chekuri, Sanjeev Khanna:
A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. 848-861 - Marek Chrobak, János Csirik, Csanád Imreh, John Noga, Jirí Sgall
The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts. 862-874 - Aleksei V. Fishkin, Klaus Jansen, Lorant Porkolab:
On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates. 875-886 - Gerhard J. Woeginger:
On the Approximability of Average Completion Time Scheduling under Precedence Constraints. 887-897
Secure Computation
- Birgit Baum-Waidner:
Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds. 898-911 - Amos Beimel, Yuval Ishai:
Information-Theoretic Private Information Retrieval: A Unified Construction. 912-926 - Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca N. Wright:
Secure Multiparty Computation of Approximations. 927-938 - Aggelos Kiayias, Moti Yung:
Secure Games with Polynomial Expressions. 939-950
Specification and Deduction
- Miquel Bofill, Guillem Godoy:
On the Completeness of Arbitrary Selection Strategies for Paramodulation. 951-962 - Furio Honsell, Marino Miculan
An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS. 963-978 - Konstantin Korovin, Andrei Voronkov:
Knuth-Bendix Constraint Solving Is NP-Complete. 979-992 - Lutz Schröder
Amalgamation in CASL via Enriched Signatures. 993-1004
Structural Complexity
- Albert Atserias, Maria Luisa Bonet, Juan Luis Esteban
Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution. 1005-1016 - Harry Buhrman, John Tromp, Paul M. B. Vitányi:
Time and Space Bounds for Reversible Simulation. 1017-1027 - Jack Jie Dai, James I. Lathrop, Jack H. Lutz, Elvira Mayordomo:
Finite-State Dimension. 1028-1039 - Lane A. Hemaspaandra
The Complexity of Computing the Size of an Interval. 1040-1051 - Tomasz Jurdzinski, Miroslaw Kutylowski:
Communication Gap for Finite Memory Devices. 1052-1064 - Rocco A. Servedio:
Separating Quantum and Classical Learning. 1065-1080
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-11-25 22:32 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: