Ebook: Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings

This book constitutes the thoroughly refereed conference proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, held in Klosterneuburg, Austria, in August 2013. The 67 revised full papers presented together with six invited talks were carefully selected from 191 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.

---

This book constitutes the thoroughly refereed conference proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, held in Klosterneuburg, Austria, in August 2013. The 67 revised full papers presented together with six invited talks were carefully selected from 191 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.

---

This book constitutes the thoroughly refereed conference proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, held in Klosterneuburg, Austria, in August 2013. The 67 revised full papers presented together with six invited talks were carefully selected from 191 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.
Content:
Front Matter....Pages -
Alternation Trading Proofs and Their Limitations....Pages 1-7
Bin Packing Games with Selfish Items....Pages 8-21
A Constructive Proof of the Topological Kruskal Theorem....Pages 22-41
Logical and Structural Approaches to the Graph Isomorphism Problem....Pages 42-42
Prior-Free Auctions of Digital Goods....Pages 43-44
Synthesis from Temporal Specifications: New Applications in Robotics and Model-Driven Development....Pages 45-49
Clustering on k-Edge-Colored Graphs....Pages 50-61
How to Pack Your Items When You Have to Buy Your Knapsack....Pages 62-73
Computing Behavioral Distances, Compositionally....Pages 74-85
Which Finitely Ambiguous Automata Recognize Finitely Sequential Functions?....Pages 86-97
Rewriting Guarded Negation Queries....Pages 98-110
Parity Games and Propositional Proofs....Pages 111-122
Logic and Branching Automata....Pages 123-134
A Constant Factor Approximation for the Generalized Assignment Problem with Minimum Quantities and Unit Size Items....Pages 135-145
Determinacy and Rewriting of Top-Down and MSO Tree Transformations....Pages 146-158
On the Speed of Constraint Propagation and the Time Complexity of Arc Consistency Testing....Pages 159-170
Validity of Tree Pattern Queries with Respect to Schema Information....Pages 171-182
Auctions for Partial Heterogeneous Preferences....Pages 183-194
New Polynomial Cases of the Weighted Efficient Domination Problem....Pages 195-206
Bringing Order to Special Cases of Klee’s Measure Problem....Pages 207-218
Random Shortest Paths: Non-euclidean Instances for Metric Optimization Problems....Pages 219-230
Semilinearity and Context-Freeness of Languages Accepted by Valence Automata....Pages 231-242
Learning Reductions to Sparse Sets....Pages 243-253
Probabilistic Automata with Isolated Cut-Points....Pages 254-265
On Stochastic Games with Multiple Objectives....Pages 266-277
Minimal Indices for Successor Search....Pages 278-289
Paradigms for Parameterized Enumeration....Pages 290-301
Complexity of Checking Bisimilarity between Sequential and Parallel Processes....Pages 302-313
Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results....Pages 314-324
Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees....Pages 325-336
Noninterference with Local Policies....Pages 337-348
In-Place Binary Counters....Pages 349-360
Rent or Buy Problems with a Fixed Time Horizon....Pages 361-372
On the Recognition of Four-Directional Orthogonal Ray Graphs....Pages 373-384
Reachability Analysis of Recursive Quantum Markov Chains....Pages 385-396
Ordering Metro Lines by Block Crossings....Pages 397-408
Reachability in Register Machines with Polynomial Updates....Pages 409-420
On the Parameterized Complexity of Cutting a Few Vertices from a Graph....Pages 421-432
On Fixed-Polynomial Size Circuit Lower Bounds for Uniform Polynomials in the Sense of Valiant....Pages 433-444
A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems....Pages 445-456
Meta-kernelization with Structural Parameters....Pages 457-468
Separating Hierarchical and General Hub Labelings....Pages 469-479
On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem....Pages 480-491
A Note on Deterministic Poly-Time Algorithms for Partition Functions Associated with Boolean Matrices with Prescribed Row and Column Sums....Pages 492-503
Polynomial Threshold Functions and Boolean Threshold Circuits....Pages 504-515
Reachability in Higher-Order-Counters....Pages 516-527
Length-Increasing Reductions for PSPACE-Completeness....Pages 528-539
A Polychromatic Ramsey Theory for Ordinals....Pages 540-550
Detecting Regularities on Grammar-Compressed Strings....Pages 551-558
Small Depth Proof Systems....Pages 559-570
Reversibility of Computations in Graph-Walking Automata....Pages 571-582
Prime Languages....Pages 583-594
Logical Aspects of the Lexicographic Order on 1-Counter Languages....Pages 595-606
Helly Circular-Arc Graph Isomorphism Is in Logspace....Pages 607-618
Zeno, Hercules and the Hydra: Downward Rational Termination Is Ackermannian....Pages 619-630
Strong Completeness for Markovian Logics....Pages 631-642
Arithmetic Branching Programs with Memory....Pages 643-654
Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?....Pages 655-666
Unlimited Decidability of Distributed Synthesis with Limited Missing Knowledge....Pages 667-678
Revisiting Space in Proof Complexity: Treewidth and Pathwidth....Pages 679-690
Space-Efficient Parallel Algorithms for Combinatorial Search Problems....Pages 691-703
Separating Regular Languages by Piecewise Testable and Unambiguous Languages....Pages 704-716
An Unusual Temporal Logic....Pages 717-728
A More Efficient Simulation Algorithm on Kripke Structures....Pages 729-740
A Planarity Test via Construction Sequences....Pages 741-752
Feasible Combinatorial Matrix Theory....Pages 753-764
Approximation Algorithms for Generalized Plant Location....Pages 765-776
Hardness of Classically Simulating Quantum Circuits with Unbounded Toffoli and Fan-Out Gates....Pages 777-788
Improved Bounds for Reduction to Depth 4 and Depth 3....Pages 789-800
Parameterized Algorithms for Module Motif....Pages 801-812
On the Quantifier-Free Dynamic Complexity of Reachability....Pages 813-824
Back Matter....Pages 825-836
....Pages 837-848