This volume constitutes the refereed proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010, held in Brno, Czech Republic, in August 2010. The 56 revised full papers presented together with 5 invited talks were carefully reviewed and selected from 149 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, grammars and formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, cryptography and security, databases and knowledge-based systems, formal specifications and program development, foundations of computing, logic in computer science, mobile computing, models of computation, networks, parallel and distributed computing, quantum computing, semantics and verification of programs, and theoretical issues in artificial intelligence.
Author(s): Andris Ambainis (auth.), Petr Hliněný, Antonín Kučera (eds.)
Series: Lecture Notes in Computer Science 6281 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 714
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Computation by Abstract Devices; Data Structures; Mathematical Logic and Formal Languages; Logics and Meanings of Programs
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 -
