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

Front Cover
Petr Hlineny, Antonin Kucera
Springer Science & Business Media, Aug 10, 2010 - Computers - 714 pages
The 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
Author Index
713
Copyright

Other editions - View all

Common terms and phrases