default search action
26th STACS 2009: Freiburg, Germany
- Susanne Albers, Jean-Yves Marion:
26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings. LIPIcs 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009, ISBN 978-3-939897-09-5 - Susanne Albers, Jean-Yves Marion:
Preface - 26th International Symposium on Theoretical Aspects of Computer Science.
Invited Papers
- Eda Baykan, Monika Henzinger, Stefan F. Keller, Sebastian De Castelberg, Markus Kinzler:
A Comparison of Techniques for Sampling Web Pages. 13-30 - Jean-Eric Pin:
Profinite Methods in Automata Theory. 31-50 - Nicole Schweikardt:
Lower Bounds for Multi-Pass Processing of Multiple Data Streams. 51-61
Contributed Papers
- Mustaq Ahmed, Anna Lubiw:
Shortest Paths Avoiding Forbidden Subpaths. 63-74 - Joël Alwen, Chris Peikert:
Generating Shorter Bases for Hard Random Lattices. 75-86 - Vikraman Arvind, Partha Mukhopadhyay:
Quantum Query Complexity of Multilinear Identity Testing. 87-98 - Nathalie Aubrun, Mathieu Sablik:
An Order on Sets of Tilings Corresponding to an Order on Languages. 99-110 - Jérémy Barbay, Gonzalo Navarro:
Compressed Representations of Permutations, and Applications. 111-122 - Frédérique Bassino, Julien David, Cyril Nicaud:
On the Average Complexity of Moore's State Minimization Algorithm. 123-134 - Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing Linear-Invariant Non-Linear Properties. 135-146 - Laurent Bienvenu, Rod Downey:
Kolmogorov Complexity and Solovay Functions. 147-158 - Mikolaj Bojanczyk:
Weak MSO with the Unbounding Quantifier. 159-170 - Glencora Borradaile, Erik D. Demaine, Siamak Tazari:
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. 171-182 - Nicolas Bousquet, Jean Daligault, Stéphan Thomassé, Anders Yeo:
A Polynomial Kernel for Multicut in Trees. 183-194 - Laurent Boyer, Guillaume Theyssier:
On Local Symmetries and Universality in Cellular Automata. 195-206 - Tomás Brázdil, Václav Brozek, Antonín Kucera, Jan Obdrzálek:
Qualitative Reachability in Stochastic BPA Games. 207-218 - Jop Briët, Ronald de Wolf:
Locally Decodable Quantum Codes. 219-230 - Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating Homomorphisms. 231-242 - Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster:
Hardness and Algorithms for Rainbow Connectivity. 243-254 - Ho-Leung Chan, Jeff Edmonds, Tak Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, Kirk Pruhs:
Nonclairvoyant Speed Scaling for Flow and Energy. 255-264 - Victor Chepoi, Morgan Seston:
An Approximation Algorithm for linfinity Fitting Robinson Structures to Distances. 265-276 - Mahdi Cheraghchi
, Amin Shokrollahi:
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties. 277-288 - Julien Clément, Maxime Crochemore, Giuseppina Rindone:
Reverse Engineering Prefix Tables. 289-300 - Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam:
The Price of Anarchy in Cooperative Network Creation Games. 301-312 - Ronald de Wolf:
Error-Correcting Data Structures. 313-324 - Volker Diekert, Manfred Kufleitner:
Fragments of First-Order Logic over Infinite Words. 325-336 - Pietro di Lena, Luciano Margara:
Undecidable Properties of Limit Set Dynamics of Cellular Automata. 337-347 - Tomás Ebenlendr, Jirí Sgall:
Semi-Online Preemptive Scheduling: One Algorithm for All Variants. 349-360 - Khaled M. Elbassioni, Erik Krohn, Domagoj Matijevic, Julián Mestre, Domagoj Severdija:
Improved Approximations for Guarding 1.5-Dimensional Terrains. 361-371 - Robert Elsässer, Thomas Sauerwald:
Cover Time and Broadcast Time. 373-384 - Matthias Englert, Heiko Röglin, Jacob Spönemann, Berthold Vöcking:
Economical Caching. 385-396 - Babak Farzad, Lap Chi Lau, Van Bang Le, Nguyen Ngoc Tuy:
Computing Graph Roots Without Short Cycles. 397-408 - Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier:
A Generalization of Nemhauser and Trotter's Local Optimization Theorem. 409-420 - Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, Yngve Villanger:
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. 421-432 - Alain Finkel, Jean Goubault-Larrecq:
Forward Analysis for WSTS, Part I: Completions. 433-444 - Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos:
Approximating Acyclicity Parameters of Sparse Hypergraphs. 445-456 - Gianni Franceschini, Roberto Grossi, S. Muthukrishnan:
Optimal Cache-Aware Suffix Selection. 457-468 - Péter Gács, Mathieu Hoyrup, Cristobal Rojas:
Randomness on Computable Probability Spaces - A Dynamical Point of View. 469-480 - Wouter Gelade, Marcel Marquardt, Thomas Schwentick:
The Dynamic Complexity of Formal Languages. 481-492 - Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley:
A Complexity Dichotomy for Partition Functions with Mixed Signs. 493-504 - André Gronemeier:
Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness. 505-516 - Roberto Grossi, Alessio Orlandi, Rajeev Raman, S. Srinivasa Rao:
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries. 517-528 - Danny Hermelin, Gad M. Landau, Shir Landau, Oren Weimann:
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression. 529-540 - Florian Horn:
Random Fruits on the Zielonka Tree. 541-552 - Juraj Hromkovic, Georg Schnitger:
Ambiguity and Communication. 553-564 - Szczepan Hummel, Henryk Michalewski, Damian Niwinski:
On the Borel Inseparability of Game Tree Languages. 565-575 - Artur Jez, Alexander Okhotin:
Equations over Sets of Natural Numbers with Addition Only. 577-588 - Daniel Kirsten, Sylvain Lombardy:
Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata. 589-600 - Stefan Kratsch:
Polynomial Kernelizations for MIN F+Pi1 and MAX NP. 601-612 - Fabian Kuhn:
Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time. 613-624 - François Le Gall:
Efficient Isomorphism Testing for a Class of Group Extensions. 625-636 - Bodo Manthey:
On Approximating Multi-Criteria TSP. 637-648 - Dániel Marx:
Tractable Structures for Constraint Satisfaction with Truth Tables. 649-660 - Sven Schewe
Büchi Complementation Made Tight. 661-672 - Lutz Schröder, Dirk Pattinson:
Strong Completeness of Coalgebraic Modal Logics. 673-684 - Kenya Ueno:
A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints. 685-696 - Marius Zimand:
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. 697-708
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 2025-11-14 22:25 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: