26. STACS 2009: Freiburg, Germany

• Susanne Albers, Jean-Yves Marion:
  Preface - 26th International Symposium on Theoretical Aspects of Computer Science. 0-
  

Invited Papers

• Eda Baykan, Monika Rauch 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 Briet, 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 l_infinity 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, Jiri 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
  
• Andre 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⁺Pi₁ and MAX NP. 601-612
  
• Fabian Kuhn:
  Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time. 613-624
  
• Francois 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