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

Front Cover
Springer Science & Business Media, Aug 12, 2008 - Computers - 626 pages

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.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

One Useful Logic That Defines Its Own Truth
1
On Synchronous and Asynchronous Interaction in Distributed Systems
16
A Robust Class of Regular Languages
36
Deterministic Models of Communication Faults
52
Algebraic Graph Algorithms
68
QuestionAnswer Games on Towers and Pyramids
83
The Maximum Independent Set Problem in Planar Graphs
96
Graphical Multicast Cost Sharing Games
108
Iterative Compression and Exact Algorithms
335
Complexity and Limiting Ratio of Boolean Functions over Implication
347
Succinctness of Regular Expressions with Interleaving Intersection and Counting
363
Nilpotency and Limit Sets of Cellular Automata
375
A Note on itkColorability of itP_5Free Graphs
387
Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations
395
Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
407
Periodicity and Immortality in Reversible Computing
419

Shortest Synchronizing Strings for Huffman Codes
120
Optimizing Conjunctive Queries over Trees Using Schema Information
132
Clustering with Partial Information
144
Reoptimization of the Metric Deadline TSP
156
On the Shortest Linear StraightLine Program for Computing Linear Forms
168
Flip Algorithm for Segment Triangulations
180
Computing Sharp 2Factors in ClawFree Graphs
193
A 65Approximation Algorithm for the Maximum 3Cover Problem
205
Positional Strategies for HigherOrder Pushdown Parity Games
217
Arthur and Merlin as Oracles
229
A Decision Problem for Ultimately Periodic Sets in Nonstandard Numeration Systems
241
A Unifying Approach to Picture Grammars
253
On a Special Class of Primitive Words
265
Complexity of Data Tree Patterns over XML Documents
278
A PTAS for the Sparsest Spanners Problem on ApexMinorFree Graphs
290
Computational Complexity of PerfectPhylogenyRelated Haplotyping Problems
299
SincereStrategy PreferenceBased Approval Voting Broadly Resists Control
311
ReversalBounded Counter Machines Revisited
323
StepOut Ring Signatures
431
The Height of Factorization Forests
443
Arithmetic Circuits Syntactic Multilinearity and the Limitations of Skew Formulae
455
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
467
From lambdaCalculus to Universal Algebra and Back
479
A Complete Axiomatic System for a ProcessBased Spatial Logic
491
Voronoi Games on Cycle Graphs
503
Colouring Random Empire Trees
515
A Random Oracle Does Not Help Extract the Mutual Information
527
Approximating Independent Set and Coloring in Random Uniform Hypergraphs
539
A GraphTheoretic Approach
551
Directed Percolation Arising in Stochastic Cellular Automata Analysis
563
Resolution Width and Cutting Plane Rank Are Incomparable
575
On the Decidability of Bounded Valuedness for Transducers Extended Abstract
588
Monadic Second Order Logic on Graphs with Local Cardinality Constraints
601
Short Proofs of Strong Normalization
613
Author Index
624
Copyright

Other editions - View all

Common terms and phrases