33. MFCS 2008: Torun, Poland

Invited Papers

• Andreas Blass, Yuri Gurevich:
  One Useful Logic That Defines Its Own Truth. 1-15
  
• Rob J. van Glabbeek, Ursula Goltz, Jens-Wolfhard Schicke:
  On Synchronous and Asynchronous Interaction in Distributed Systems. 16-35
  
• Antonio Cano Gómez, Jean-Eric Pin:
  A Robust Class of Regular Languages. 36-51
  
• Rastislav Kralovic, Richard Královic:
  Deterministic Models of Communication Faults. 52-67
  
• Piotr Sankowski:
  Algebraic Graph Algorithms. 68-82
  

Contributed Papers

• Sarmad Abbasi, Numan Sheikh:
  Question/Answer Games on Towers and Pyramids. 83-95
  
• Vladimir E. Alekseev, Vadim V. Lozin, Dmitriy Malyshev, Martin Milanic:
  The Maximum Independent Set Problem in Planar Graphs. 96-107
  
• Vittorio Bilò, Angelo Fanelli, Michele Flammini, Luca Moscardelli:
  When Ignorance Helps: Graphical Multicast Cost Sharing Games. 108-119
  
• Marek Tomasz Biskup:
  Shortest Synchronizing Strings for Huffman Codes. 120-131
  
• Henrik Björklund, Wim Martens, Thomas Schwentick:
  Optimizing Conjunctive Queries over Trees Using Schema Information. 132-143
  
• Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, Frances A. Rosamond:
  Clustering with Partial Information. 144-155
  
• Hans-Joachim Böckenhauer, Dennis Komm:
  Reoptimization of the Metric Deadline TSP. 156-167
  
• Joan Boyar, Philip Matthews, René Peralta:
  On the Shortest Linear Straight-Line Program for Computing Linear Forms. 168-179
  
• Mathieu Brévilliers, Nicolas Chevallier, Dominique Schmitt:
  Flip Algorithm for Segment Triangulations. 180-192
  
• Hajo Broersma, Daniël Paulusma:
  Computing Sharp 2-Factors in Claw-Free Graphs. 193-204
  
• Ioannis Caragiannis, Gianpiero Monaco:
  A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem. 205-216
  
• Arnaud Carayol, Michaela Slaats:
  Positional Strategies for Higher-Order Pushdown Parity Games. 217-228
  
• Venkatesan T. Chakaravarthy, Sambuddha Roy:
  Arthur and Merlin as Oracles. 229-240
  
• Emilie Charlier, Michel Rigo:
  A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems. 241-252
  
• Alessandra Cherubini, Stefano Crespi-Reghizzi, Matteo Pradella:
  Regional Languages and Tiling: A Unifying Approach to Picture Grammars. 253-264
  
• Elena Czeizler, Lila Kari, Shinnosuke Seki:
  On a Special Class of Primitive Words. 265-277
  
• Claire David:
  Complexity of Data Tree Patterns over XML Documents. 278-289
  
• Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach:
  A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs. 290-298
  
• Michael Elberfeld, Till Tantau:
  Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems. 299-310
  
• Gábor Erdélyi, Markus Nowak, Jörg Rothe:
  Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control. 311-322
  
• Alain Finkel, Arnaud Sangnier:
  Reversal-Bounded Counter Machines Revisited. 323-334
  
• Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh:
  Iterative Compression and Exact Algorithms. 335-346
  
• Hervé Fournier, Danièle Gardy, Antoine Genitrini, Bernhard Gittenberger:
  Complexity and Limiting Ratio of Boolean Functions over Implication. 347-362
  
• Wouter Gelade:
  Succinctness of Regular Expressions with Interleaving, Intersection and Counting. 363-374
  
• Pierre Guillon, Gaétan Richard:
  Nilpotency and Limit Sets of Cellular Automata. 375-386
  
• Chính T. Hoàng, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, Xiao Shu:
  A Note on k-Colorability of P5-Free Graphs. 387-394
  
• Christian Hundt, Maciej Liskiewicz:
  Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations. 395-406
  
• Maurice J. Jansen:
  Lower Bounds for Syntactically Multilinear Algebraic Branching Programs. 407-418
  
• Jarkko Kari, Nicolas Ollinger:
  Periodicity and Immortality in Reversible Computing. 419-430
  
• Marek Klonowski, Lukasz Krzywiecki, Miroslaw Kutylowski, Anna Lauks:
  Step-Out Ring Signatures. 431-442
  
• Manfred Kufleitner:
  The Height of Factorization Forests. 443-454
  
• Meena Mahajan, B. V. Raghavendra Rao:
  Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae. 455-466
  
• Bodo Manthey, Till Tantau:
  Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise. 467-478
  
• Giulio Manzonetto, Antonino Salibra:
  From lambda-Calculus to Universal Algebra and Back. 479-490
  
• Radu Mardare, Alberto Policriti:
  A Complete Axiomatic System for a Process-Based Spatial Logic. 491-502
  
• Marios Mavronicolas, Burkhard Monien, Vicky G. Papadopoulou, Florian Schoppmann:
  Voronoi Games on Cycle Graphs. 503-514
  
• Andrew R. A. McGrae, Michele Zito:
  Colouring Random Empire Trees. 515-526
  
• Andrei A. Muchnik, Andrei E. Romashchenko:
  A Random Oracle Does Not Help Extract the Mutual Information. 527-538
  
• Kai Plociennik:
  Approximating Independent Set and Coloring in Random Uniform Hypergraphs. 539-550
  
• Daniel Raible, Henning Fernau:
  A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach. 551-562
  
• Damien Regnault:
  Directed Percolation Arising in Stochastic Cellular Automata Analysis. 563-574
  
• Mark Rhodes:
  Resolution Width and Cutting Plane Rank Are Incomparable. 575-587
  
• Jacques Sakarovitch, Rodrigo de Souza:
  On the Decidability of Bounded Valuedness for Transducers. 588-600
  
• Stefan Szeider:
  Monadic Second Order Logic on Graphs with Local Cardinality Constraints. 601-612
  
• Aleksander Wojdyga:
  Short Proofs of Strong Normalization. 613-623