Andreas Blass, Yuri Gurevich (auth.), Edward Ochmański, Jerzy Tyszkiewicz (eds.)3540852379, 9783540852377
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.
Table of contents :
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 –
Reviews
There are no reviews yet.