Mathematical Foundations of Computer Science 2012: 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings

Front Matter....Pages -
On the Complexity of Ontological Reasoning under Disjunctive Existential Rules....Pages 1-18
New Races in Parameterized Algorithmics....Pages 19-30
Scott Is Always Simple....Pages 31-45
A Toolkit for Proving Limitations of the Expressive Power of Logics....Pages 46-47
How to Reconstruct a Genome....Pages 48-48
Simple Models for Recursive Schemes....Pages 49-60
Transportation under Nasty Side Constraints....Pages 61-62
Computation of Least Fixed Points....Pages 63-63
Unordered Constraint Satisfaction Games....Pages 64-75
A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree....Pages 76-87
Reductions to the Set of Random Strings: The Resource-Bounded Case....Pages 88-99
Approximate Graph Isomorphism....Pages 100-111
Near-Optimal Expanding Generator Sets for Solvable Permutation Groups....Pages 112-123
Generating Functions of Timed Languages....Pages 124-135
The Robust Set Problem: Parameterized Complexity and Approximation....Pages 136-147
Mortality for 2 ×2 Matrices Is NP-Hard....Pages 148-159
Solving Counter Parity Games....Pages 160-171
Drawing Planar Graphs on Points Inside a Polygon....Pages 172-183
New Advances in Reoptimizing the Minimum Steiner Tree Problem....Pages 184-197
Smoothed Complexity Theory....Pages 198-209
Abelian Pattern Avoidance in Partial Words....Pages 210-221
The Complexity of Rerouting Shortest Paths....Pages 222-233
Computing with Large Populations Using Interactions....Pages 234-246
Pancake Flipping Is Hard....Pages 247-258
In-place Heap Construction with Optimized Comparisons, Moves, and Cache Misses....Pages 259-270
Model Checking Stochastic Branching Processes....Pages 271-282
Parameterized Study of the Test Cover Problem....Pages 283-295
Sitting Closer to Friends Than Enemies, Revisited....Pages 296-307
A Dichotomy Theorem for Homomorphism Polynomials....Pages 308-322
Finite State Transducers for Modular Möbius Number Systems....Pages 323-334
Zero-Knowledge Proofs via Polynomial Representations....Pages 335-347
Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width....Pages 348-359
On the Impact of Fair Best Response Dynamics....Pages 360-371
Fast Balanced Partitioning Is Hard Even on Grids and Trees....Pages 372-382
A Characterization of Bispecial Sturmian Words....Pages 383-394
Online Sum-Radii Clustering....Pages 395-406
Observe and Remain Silent (Communication-Less Agent Location Discovery)....Pages 407-418
When Trees Grow Low: Shrubs and Fast MSO 1 ....Pages 419-430
Strategy Machines and Their Complexity....Pages 431-442
Coloring Graphs Characterized by a Forbidden Subgraph....Pages 443-454
Obtaining Planarity by Contracting Few Edges....Pages 455-466
Light Spanners in Bounded Pathwidth Graphs....Pages 467-477
Planarizing Gadgets for Perfect Matching Do Not Exist....Pages 478-490
Kernels for Edge Dominating Set: Simpler or Smaller....Pages 491-502
Categories of Coalgebraic Games....Pages 503-515
Quasi-recognizable vs MSO Definable Languages of One-Dimensional Overlapping Tiles....Pages 516-528
An Improved Approximation Scheme for Variable-Sized Bin Packing....Pages 529-541
Gathering an Even Number of Robots in an Odd Ring without Global Multiplicity Detection....Pages 542-553
Reversal Hierarchies for Small 2DFAs....Pages 554-565
Strictness of the Collapsible Pushdown Hierarchy....Pages 566-577
Computational Complexity of Smooth Differential Equations....Pages 578-589
The Lower Reaches of Circuit Uniformity....Pages 590-602
The Join Levels of the Trotter-Weil Hierarchy Are Decidable....Pages 603-614
Equations X  +  A  =  B and ( X  +  X ) +  C  = ( X  −  X ) +  D over Sets of Natural Numbers....Pages 615-629
Weakly-Synchronized Ground Tree Rewriting....Pages 630-642
Descriptional Complexity of Deterministic Regular Expressions....Pages 643-654
Identity Testing, Multilinearity Testing, and Monomials in Read-Once/Twice Formulas and Branching Programs....Pages 655-667
Fine and Wilf’s Theorem and Pseudo-repetitions....Pages 668-680
Taking It to the Limit: Approximate Reasoning for Markov Processes....Pages 681-692
Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games....Pages 693-704
Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity?....Pages 705-717
Reducing a Target Interval to a Few Exact Queries....Pages 718-727
Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs....Pages 728-739
A Finite Basis for ‘Almost Future’ Temporal Logic over the Reals....Pages 740-751
Constructing Premaximal Ternary Square-Free Words of Any Level....Pages 752-763
Regularity Problems for Weak Pushdown ω -Automata and Games....Pages 764-776
Computational Aspects of Cellular Automata on Countable Sofic Shifts....Pages 777-788
Computing Lempel-Ziv Factorization Online....Pages 789-799
On Two Stronger Versions of Dejean’s Conjecture....Pages 800-812
Probabilistic Automata and Probabilistic Logic....Pages 813-824
A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments....Pages 825-835
Back Matter....Pages -