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

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 -