Mathematical Foundations of Computer Science 2008: 33rd International Symposium, MFCS 2008, Toru ́n, Poland, August 25-29, 2008. Proceedings

This book constitutes the refereed proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008, held in Torun, Poland, in August 2008. The 45 revised full papers presented together with 5 invited lectures were carefully reviewed and selected from 119 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, ranging from algorithmic game theory, algorithms and data structures, artificial intelligence, automata and formal languages, bioinformatics, complexity, concurrency and petrinets, cryptography and security, logic and formal specifications, models of computations, parallel and distributed computing, semantics and verification. 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 - Annotation This book constitutes the refereed proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008, held in Torun, Poland, in August 2008. The 45 revised full papers presented together with 5 invited lectures were carefully reviewed and selected from 119 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, ranging from algorithmic game theory, algorithms and data structures, artificial intelligence, automata and formal languages, bioinformatics, complexity, concurrency and petrinets, cryptography and security, logic and formal specifications, models of computations, parallel and distributed computing, semantics and verification