Mathematical Foundations of Computer Science 2008: 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings

Front Matter....Pages -
One Useful Logic That Defines Its Own Truth....Pages 1-15
On Synchronous and Asynchronous Interaction in Distributed Systems....Pages 16-35
A Robust Class of Regular Languages....Pages 36-51
Deterministic Models of Communication Faults....Pages 52-67
Algebraic Graph Algorithms....Pages 68-82
Question/Answer Games on Towers and Pyramids....Pages 83-95
The Maximum Independent Set Problem in Planar Graphs....Pages 96-107
When Ignorance Helps: Graphical Multicast Cost Sharing Games....Pages 108-119
Shortest Synchronizing Strings for Huffman Codes....Pages 120-131
Optimizing Conjunctive Queries over Trees Using Schema Information....Pages 132-143
Clustering with Partial Information....Pages 144-155
Reoptimization of the Metric Deadline TSP....Pages 156-167
On the Shortest Linear Straight-Line Program for Computing Linear Forms....Pages 168-179
Flip Algorithm for Segment Triangulations....Pages 180-192
Computing Sharp 2-Factors in Claw-Free Graphs....Pages 193-204
A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem....Pages 205-216
Positional Strategies for Higher-Order Pushdown Parity Games....Pages 217-228
Arthur and Merlin as Oracles....Pages 229-240
A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems....Pages 241-252
Regional Languages and Tiling: A Unifying Approach to Picture Grammars....Pages 253-264
On a Special Class of Primitive Words....Pages 265-277
Complexity of Data Tree Patterns over XML Documents....Pages 278-289
A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs....Pages 290-298
Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems....Pages 299-310
Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control....Pages 311-322
Reversal-Bounded Counter Machines Revisited....Pages 323-334
Iterative Compression and Exact Algorithms....Pages 335-346
Complexity and Limiting Ratio of Boolean Functions over Implication....Pages 347-362
Succinctness of Regular Expressions with Interleaving, Intersection and Counting....Pages 363-374
Nilpotency and Limit Sets of Cellular Automata....Pages 375-386
A Note on k -Colorability of P 5 -Free Graphs....Pages 387-394
Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations....Pages 395-406
Lower Bounds for Syntactically Multilinear Algebraic Branching Programs....Pages 407-418
Periodicity and Immortality in Reversible Computing....Pages 419-430
Step-Out Ring Signatures....Pages 431-442
The Height of Factorization Forests....Pages 443-454
Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae....Pages 455-466
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise....Pages 467-478
From λ -Calculus to Universal Algebra and Back....Pages 479-490
A Complete Axiomatic System for a Process-Based Spatial Logic....Pages 491-502
Voronoi Games on Cycle Graphs....Pages 503-514
Colouring Random Empire Trees....Pages 515-526
A Random Oracle Does Not Help Extract the Mutual Information....Pages 527-538
Approximating Independent Set and Coloring in Random Uniform Hypergraphs....Pages 539-550
A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach....Pages 551-562
Directed Percolation Arising in Stochastic Cellular Automata Analysis....Pages 563-574
Resolution Width and Cutting Plane Rank Are Incomparable....Pages 575-587
On the Decidability of Bounded Valuedness for Transducers....Pages 588-600
Monadic Second Order Logic on Graphs with Local Cardinality Constraints....Pages 601-612
Short Proofs of Strong Normalization....Pages 613-623
Back Matter....Pages -