25. STACS 2008: Bordeaux, France

• Susanne Albers, Pascal Weil:
  Abstracts Collection - 25th International Symposium on Theoretical Aspects of Computer Science. 0-
  
• Susanne Albers, Pascal Weil:
  Preface - 25th International Symposium on Theoretical Aspects of Computer Science. 1-6
  

Invited papers

• Maxime Crochemore, Lucian Ilie:
  Understanding Maximal Repetitions in Strings. 11-16
  
• Thomas Schwentick:
  A Little Bit Infinite? On Adding Data to Finitely Labelled Structures (Abstract). 17-18
  
• Mihalis Yannakakis:
  Equilibria, Fixed Points, and Complexity Classes. 19-38
  

Contributed Papers

• Pilar Albert, Elvira Mayordomo, Philippe Moser, Sylvain Perifel:
  Pushdown Compression. 39-48
  
• Andris Ambainis:
  Quantum search with variable times. 49-61
  
• Alexis Ballier, Bruno Durand, Emmanuel Jeandel:
  Structural aspects of tilings. 61-72
  
• Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Veraschagin:
  Limit complexities revisited. 73-84
  
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto:
  Trimmed Moebius Inversion and Graphs of Bounded Degree. 85-96
  
• Markus Bläser, Christian Hoffmann:
  On the Complexity of the Interlace Polynomial. 97-108
  
• Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela:
  Minimizing Flow Time in the Wireless Gathering Problem. 109-120
  
• Patricia Bouyer, Nicolas Markey, Joël Ouaknine, Ph. Schnoebelen, James Worrell:
  On Termination for Faulty Channel Machines. 121-132
  
• Patrick Briest, Martin Hoefer, Piotr Krysta:
  Stackelberg Network Pricing Games. 133-142
  
• Joshua Brody, Amit Chakrabarti:
  Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. 145-156
  
• Venkatesan T. Chakaravarthy, Sambuddha Roy:
  Finding Irrefutable Certificates for S₂^p via Arthur and Merlin. 157-168
  
• Chao Chen, Daniel Freedman:
  Quantifying Homology Classes. 169-180
  
• Éric Colin de Verdière, Alexander Schrijver:
  Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs. 181-192
  
• Atlas F. Cook, Carola Wenk:
  Geodesic Fréchet Distance Inside a Simple Polygon. 193-204
  
• Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Mohammad Sohel Rahman, Tomasz Walen:
  Improved Algorithms for the Range Next Value Problem and Applications. 205-216
  
• Mirela Damian, Robin Y. Flatland, Joseph O'Rourke, Suneeta Ramaswami:
  Connecting Polygonizations via Stretches and Twangs. 217-228
  
• Samir Datta, Raghav Kulkarni, Sambuddha Roy:
  Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs. 229-240
  
• Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel:
  Tight Bounds for Blind Search on the Integers. 241-252
  
• Jean-François Dufourd:
  Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps. 253-264
  
• Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, Alexander Wolff:
  Trimming of Graphs, with Application to Point Labeling. 265-276
  
• Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Matús Mihalák, Rajeev Raman:
  Computing Minimum Spanning Trees with Uncertainty. 277-288
  
• Javier Esparza, Stefan Kiefer, Michael Luttenberger:
  Convergence Thresholds of Newton's Method for Monotone Polynomial Equations. 289-300
  
• Diana Fischer, Erich Grädel, Lukasz Kaiser:
  Model Checking Games for the Quantitative µ-Calculus. 301-312
  
• Tobias Ganzow, Sasha Rubin:
  Order-Invariant MSO is Stronger than Counting MSO in the Finite. 313-324
  
• Wouter Gelade, Frank Neven:
  Succinctness of the Complement and Intersection of Regular Expressions. 325-336
  
• Christian Glasser, Heinz Schmitz, Victor L. Selivanov:
  Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages. 337-348
  
• Edith Hemaspaandra, Henning Schnoor:
  On the Complexity of Elementary Modal Logics. 349-360
  
• Viet Tung Hoang, Wing-Kin Sung:
  Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees. 361-372
  
• Alexander Okhotin, Artur Jez:
  Complexity of solutions of equations over sets of natural numbers. 373-384
  
• Lukasz Kaiser, Sasha Rubin, Vince Bárány:
  Cardinality and counting quantifiers on omega-automatic structures. 385-396
  
• Iyad A. Kanj, Michael J. Pelsmajer, Ge Xia, Marcus Schaefer:
  On the Induced Matching Problem. 397-408
  
• Iyad A. Kanj, Ljubomir Perkovic:
  On Geometric Spanners of Euclidean and Unit Disk Graphs. 409-420
  
• Jui-Yi Kao, Jeffrey Shallit, Zhi Xu:
  The Frobenius Problem in a Free Monoid. 421-432
  
• Jeff Kinne, Dieter van Melkebeek:
  Space Hierarchy Results for Randomized Models. 433-444
  
• Felix Klaedtke:
  Ehrenfeucht-Fraïssé Goes Automatic for Real Addition. 445-456
  
• Arist Kojevnikov, Sergey I. Nikolenko:
  New Combinatorial Complete One-Way Functions. 457-466
  
• Dietrich Kuske:
  Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic. 467-478
  
• Sören Laue:
  Geometric Set Cover and Hitting Sets for Polytopes in R³. 479-490
  
• Angsheng Li, Mingji Xia:
  A Theory for Valiant's Matchcircuits (Extended Abstract). 491-502
  
• Zvi Lotker, Boaz Patt-Shamir, Dror Rawitz:
  Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. 503-514
  
• Shachar Lovett:
  Lower bounds for adaptive linearity tests. 515-526
  
• Pinyan Lu, Changyuan Yu:
  An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. 527-538
  
• Julián Mestre:
  Lagrangian Relaxation and Partial Cover (Extended Abstract). 539-550
  
• Ulrich Meyer:
  On Dynamic Breadth-First Search in External-Memory. 551-560
  
• Marni Mishna, Mike Zabrocki:
  Analytic aspects of the shuffle product. 561-572
  
• Filip Murlak:
  Weak index versus Borel rank. 573-584
  
• Jean-Eric Pin, Pedro V. Silva:
  A Mahler's theorem for functions from words to integers. 585-596
  
• Bill Rosgen:
  Distinguishing Short Quantum Computations. 597-608
  
• Chandan Saha:
  Factoring Polynomials over Finite Fields using Balance Test. 609-620
  
• Jacques Sakarovitch, Rodrigo de Souza:
  On the decomposition of k-valued rational relations. 621-632
  
• Thomas Thierauf, Fabian Wagner:
  The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. 633-644
  
• Antti Valmari, Petri Lehtinen:
  Efficient Minimization of DFAs with Partial Transition. 645-656
  
• Johan M. M. van Rooij, Hans L. Bodlaender:
  Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set. 657-668
  
• Mariano Zelke:
  Weighted Matching in the Semi-Streaming Model. 669-680