Mathematical Foundations of Computer Science 2011: 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings

Description

This volume constitutes the refereed proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011, held in Warsaw, Poland, in August 2011. The 48 revised full papers presented together with 6 invited talks were carefully reviewed and selected from 129 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. Front Matter....Pages - Nearest Neighbor Search in High-Dimensional Spaces....Pages 1-1 Invariantization of Listings....Pages 2-2 Duality and Recognition....Pages 3-18 Some Variants of the Star Height Problem....Pages 19-33 Generic Techniques to Round SDP Relaxations....Pages 34-34 New Proofs in Graph Minors....Pages 35-35 The Least-Core of Threshold Network Flow Games....Pages 36-47 Adhesivity Is Not Enough: Local Church-Rosser Revisited....Pages 48-59 Quantitative Refinement for Weighted Modal Transition Systems....Pages 60-71 Faster Coupon Collecting via Replication with Applications in Gossiping....Pages 72-83 Verifying Proofs in Constant Depth....Pages 84-95 The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree....Pages 96-107 Model Checking Coverability Graphs of Vector Addition Systems....Pages 108-119 Hard Functions for Low-Degree Polynomials over Prime Fields....Pages 120-131 Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking....Pages 132-144 The Reachability Problem for Vector Addition System with One Zero-Test....Pages 145-157 The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed Complexity....Pages 158-169 Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains....Pages 170-181 Pattern-Guided Data Anonymization and Clustering....Pages 182-193 Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL -Complete....Pages 194-205 Energy and Mean-Payoff Parity Markov Decision Processes....Pages 206-218 The Role of Polymorphism in the Characterisation of Complexity by Soft Types....Pages 219-230 An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection....Pages 231-242 On the Use of Guards for Logics with Data....Pages 243-255 An Elementary Proof of a 3 n  −  o ( n ) Lower Bound on the Circuit Complexity of Affine Dispersers....Pages 256-265 On the Complexity of the l -diversity Problem....Pages 266-277 Infinite Synchronizing Words for Probabilistic Automata....Pages 278-289 Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs....Pages 290-302 Parity Games on Graphs with Medium Tree-Width....Pages 303-314 Satisfiability of Systems of Equations of Real Analytic Functions Is Quasi-decidable....Pages 315-326 On Minimising Automata with Errors....Pages 327-338 Contracting a Chordal Graph to a Split Graph or a Tree....Pages 339-350 Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages....Pages 351-363 A Universally Defined Undecidable Unimodal Logic....Pages 364-375 On the Approximability of Minimum Topic Connected Overlay and Its Special Instances....Pages 376-387 Can Everybody Sit Closer to Their Friends Than Their Enemies?....Pages 388-399 Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions....Pages 400-411 Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions....Pages 412-423 Size and Computation of Injective Tree Automatic Presentations....Pages 424-435 Symmetric Functions Capture General Functions....Pages 436-447 Compressed Word Problems for Inverse Monoids....Pages 448-459 Pushing for Weighted Tree Automata....Pages 460-471 Periodicity Algorithms for Partial Words....Pages 472-484 State Complexity of Operations on Input-Driven Pushdown Automata....Pages 485-496 Conflict Packing Yields Linear Vertex-Kernels for k -FAST , k -dense RTI and a Related Problem....Pages 497-507 Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence....Pages 508-519 Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach....Pages 520-531 Distributed Synthesis for Regular and Contextfree Specifications....Pages 532-543 Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols....Pages 544-555 Untimed Language Preservation in Timed Systems....Pages 556-567 Lower Bounds for Linear Decision Trees via an Energy Complexity Argument....Pages 568-579 Weak Cost Monadic Logic over Infinite Trees....Pages 580-591 Linear Problem Kernels for Planar Graph Problems with Small Distance Property....Pages 592-603 New Parameterized Algorithms for the Edge Dominating Set Problem....Pages 604-615 Back Matter....Pages -