## Mathematical Foundations of Computer Science 2010: 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010, ProceedingsThe series of MFCS symposia, organized in rotation by Poland, Slovakia, and the Czech Republic since 1972, has a long and well-established tradition. The symposiaencouragehigh-qualityresearchinallbranchesoftheoreticalcomputer science.Their broadscopeprovidesanopportunityto bring together researchers whodonotusuallymeetatspecialized conferences. The 35th International Symposium on Mathematical Foundations of C- puter Science (MFCS 2010) was organized in parallel with the 19th EACSL Annual Conference on Computer Science Logic (CSL 2010). The federated MFCS and CSL 2010 conference had shared plenary sessions and social events forallparticipants, butthescienti?cprogramandtheproceedingswereprepared independently for both events. Out of 149 regular submissions to MFCS 2010, the Program Committee - lected 56 papers for presentation at the conference and publication in this v- ume. Each paper was reviewed by at least three Program Committee members with the help of outside experts, and the actual selection was based on a sub- quent electronic discussion. In addition to the contributed papers, the scienti?c program of MFCS 2010 included ?ve MFCS and CSL plenary talks delivered by David Basin (ETH Z] urich), HerbertEdelsbrunner (IST Austria andDuke University), ErichGrad ] el (RWTH Aachen), Bojan Mohar (University of Ljubljana and Simon Fraser U- versity), andJosephSifakis (CNRS), andthree invitedMFCS lecturesby Andris Ambainis (University of Latvia), Juraj Hromkovi?c(ETHZur ] ich), and Daniel Lokshtanov (Universitetet i Bergen). We are grateful to the invited speakers for accepting our invitation and sharing their knowledge and skills with all MFCS 2010 participants. |

### What people are saying - Write a review

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

### Contents

New Developments in Quantum Algorithms | 1 |

Persistent Homology under Nonuniform Error | 12 |

Information Complexity of Online Problems | 24 |

Algorithmic Lower Bounds for Problems on Decomposable Graphs | 37 |

Do We Really Understand the Crossing Numbers? | 38 |

Divide and Conquer | 42 |

Slowly Synchronizing Automata and Digraphs | 55 |

Weights of Exact Threshold Functions | 66 |

SecondOrder Algebraic Theories | 368 |

Frame Definability for Classes of Trees in the mucalculus | 381 |

Evaluating Nonsquare Sparse Bilinear Forms on Multiple Vector Pairs in the IOModel | 393 |

Finding and Counting VertexColored Subtrees | 405 |

Limiting Negations in Bounded Treewidth and Upward Planar Circuits | 417 |

On the Topological Complexity of MSO+U and Related Automata Models | 429 |

Least and Greatest Solutions of Equations over Sets of Integers | 441 |

Improved Simulation of Nondeterministic Turing Machines | 453 |

Proof Systems and Transformation Games | 78 |

Scheduling RealTime MixedCriticality Jobs | 90 |

A sc dexptimeComplete DolevYao Theory with Distributive Encryption | 102 |

On Problem Kernels for PossibleWinner Determination under the kApproval Protocol | 114 |

Counting Minimum s tCuts in Weighted Planar Graphs in Polynomial Time | 126 |

Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree | 138 |

Improved Approximability and Nonapproximability Results for Graph Diameter Decreasing Problems | 150 |

Distance Constraint Satisfaction Problems | 162 |

Faster Algorithms on Branch and Clique Decompositions | 174 |

Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 01 Networks | 186 |

Robust Computations with Dynamical Systems | 198 |

On Factor Universality in Symbolic Spaces | 209 |

Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity | 221 |

Resource Combinatory Algebras | 233 |

Randomness for Free | 246 |

Qualitative Analysis of PartiallyObservable Markov Decision Processes | 258 |

All Symmetric Predicates in NSPACEn2 AreStably Computable by the Mediated Population Protocol Model | 270 |

Online Clustering with Variable Sized Clusters | 282 |

Deterministic Rendezvous of Asynchronous BoundedMemory Agents in Polygonal Terrains | 294 |

Counting Classes and the Fine Structure between NC1 and L | 306 |

The Average Complexity of Moores StateMinimization Algorithm Is O n log log n | 318 |

Connected Searching of Weighted Trees | 330 |

Iterated Regret Minimization in Game Graphs | 342 |

Properties of Visibly Pushdown Transducers | 355 |

The PrizeCollecting Edge Dominating Set Problem in Trees | 465 |

The Multivariate Resultant Is NPhard in Any Characteristic | 477 |

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems | 489 |

MetaEnvyFree CakeCutting Protocols | 501 |

Two Variables and Two Successors | 513 |

Harnessing pdfMLF with the Power of System pdfSF | 525 |

Describing Average and LongtimeBehavior by Weighted MSO Logics | 537 |

Solving sc min ones 2sat as Fast as sc vertex cover | 549 |

Unambiguous Finite Automata over a Unary Alphabet | 556 |

The Complexity of Finding Reset Words in Finite Automata | 568 |

Does Treewidth Help in Modal Satisfiability? | 580 |

Asynchronous OmegaRegular Games with Partial Information | 592 |

Parity Games with Partial Information Played on Graphs of Bounded Complexity | 604 |

Revisiting AckermannHardness for Lossy Counter Machines and Reset Petri Nets | 616 |

Enumeration of the Monomials of a Polynomial and Related Complexity Classes | 629 |

Faster Approximation Schemes and Parameterized Algorithms on HMinorFree and OddMinorFree Graphs | 641 |

Semilinear Parikh Images of Regular Expressions via Reduction | 653 |

Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds | 665 |

Mesh Deformation of Dynamic Smooth Manifolds with Surface Correspondences | 677 |

Counting Dependent and Independent Strings | 689 |

Impossibility of Independence Amplification in Kolmogorov Complexity Theory | 701 |

713 | |

### Other editions - View all

### Common terms and phrases

agents algebraic algorithm almost-sure alphabet assignment automata automaton Boolean function circuit cluster competitive ratio compute consider constraint construction contains corresponding counter machines decomposition define deﬁned deﬁnition denote deterministic diﬀerent dominating set dominating set problem edge envy-free equations equivalent exists exponential ﬁnd ﬁnite ﬁrst ﬁxed ﬂow formula function f given graph G Heidelberg hypergraph iﬀ inﬁnite input integer kernel Kolmogorov complexity labeled language Lemma length linear LNCS logic lower bound machine matrix MFCS minimal monomials multiset node NP-complete NP-hard obtain online algorithm optimal parameterized complexity partial path planar player polynomial POMDPs positive problem proof Proposition protocol prove quantum randomized reachability reduction relation reset word satisﬁes sequence simulation solution Springer strings subset Theorem theory transformations transition tree treewidth Turing machine upper bound variables vector vertex vertices weighted winning strategy