Mathematical Foundations of Computer Science 2010: 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings

Front Matter....Pages -
New Developments in Quantum Algorithms....Pages 1-11
Persistent Homology under Non-uniform Error....Pages 12-23
Information Complexity of Online Problems....Pages 24-36
Algorithmic Lower Bounds for Problems on Decomposable Graphs....Pages 37-37
Do We Really Understand the Crossing Numbers?....Pages 38-41
Balanced Queries: Divide and Conquer....Pages 42-54
Slowly Synchronizing Automata and Digraphs....Pages 55-65
Weights of Exact Threshold Functions....Pages 66-77
Proof Systems and Transformation Games....Pages 78-89
Scheduling Real-Time Mixed-Criticality Jobs....Pages 90-101
A dexptime -Complete Dolev-Yao Theory with Distributive Encryption....Pages 102-113
On Problem Kernels for Possible Winner Determination under the k -Approval Protocol....Pages 114-125
Counting Minimum ( s , t )-Cuts in Weighted Planar Graphs in Polynomial Time....Pages 126-137
Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree....Pages 138-149
Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems....Pages 150-161
Distance Constraint Satisfaction Problems....Pages 162-173
Faster Algorithms on Branch and Clique Decompositions....Pages 174-185
Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks....Pages 186-197
Robust Computations with Dynamical Systems....Pages 198-208
On Factor Universality in Symbolic Spaces....Pages 209-220
Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity....Pages 221-232
Resource Combinatory Algebras....Pages 233-245
Randomness for Free....Pages 246-257
Qualitative Analysis of Partially-Observable Markov Decision Processes....Pages 258-269
All Symmetric Predicates in NSPACE ( n 2 ) Are Stably Computable by the Mediated Population Protocol Model....Pages 270-281
Online Clustering with Variable Sized Clusters....Pages 282-293
Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains....Pages 294-305
Counting Classes and the Fine Structure between NC 1 and L ....Pages 306-317
The Average Complexity of Moore’s State Minimization Algorithm Is O ( n loglog n )....Pages 318-329
Connected Searching of Weighted Trees....Pages 330-341
Iterated Regret Minimization in Game Graphs....Pages 342-354
Properties of Visibly Pushdown Transducers....Pages 355-367
Second-Order Algebraic Theories....Pages 368-380
Frame Definability for Classes of Trees in the μ -calculus....Pages 381-392
Evaluating Non-square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model....Pages 393-404
Finding and Counting Vertex-Colored Subtrees....Pages 405-416
Limiting Negations in Bounded Treewidth and Upward Planar Circuits....Pages 417-428
On the Topological Complexity of MSO+U and Related Automata Models....Pages 429-440
Least and Greatest Solutions of Equations over Sets of Integers....Pages 441-452
Improved Simulation of Nondeterministic Turing Machines....Pages 453-464
The Prize-Collecting Edge Dominating Set Problem in Trees....Pages 465-476
The Multivariate Resultant Is NP -hard in Any Characteristic....Pages 477-488
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems....Pages 489-500
Meta-Envy-Free Cake-Cutting Protocols....Pages 501-512
Two Variables and Two Successors....Pages 513-524
Harnessing ML F with the Power of System F ....Pages 525-536
Describing Average- and Longtime-Behavior by Weighted MSO Logics....Pages 537-548
Solving minones-2-sat as Fast as vertex cover ....Pages 549-555
Unambiguous Finite Automata over a Unary Alphabet....Pages 556-567
The Complexity of Finding Reset Words in Finite Automata....Pages 568-579
Does Treewidth Help in Modal Satisfiability?....Pages 580-591
Asynchronous Omega-Regular Games with Partial Information....Pages 592-603
Parity Games with Partial Information Played on Graphs of Bounded Complexity....Pages 604-615
Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets....Pages 616-628
Enumeration of the Monomials of a Polynomial and Related Complexity Classes....Pages 629-640
Faster Approximation Schemes and Parameterized Algorithms on H -Minor-Free and Odd-Minor-Free Graphs....Pages 641-652
Semi-linear Parikh Images of Regular Expressions via Reduction....Pages 653-664
Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds....Pages 665-676
Mesh Deformation of Dynamic Smooth Manifolds with Surface Correspondences....Pages 677-688
Counting Dependent and Independent Strings....Pages 689-700
Impossibility of Independence Amplification in Kolmogorov Complexity Theory....Pages 701-712
Back Matter....Pages -