Mathematical Foundations of Computer Science 2013

1. Front Matter

   PDF

2. Alternation Trading Proofs and Their Limitations

   • Sam Buss

   Pages 1-7

3. Bin Packing Games with Selfish Items

   • Leah Epstein

   Pages 8-21

4. A Constructive Proof of the Topological Kruskal Theorem

   • Jean Goubault-Larrecq

   Pages 22-41

5. Logical and Structural Approaches to the Graph Isomorphism Problem

   • Martin Grohe

   Pages 42-42

6. Prior-Free Auctions of Digital Goods

   • Elias Koutsoupias

   Pages 43-44

7. Synthesis from Temporal Specifications: New Applications in Robotics and Model-Driven Development

   • Nir Piterman

   Pages 45-49

8. Clustering on k-Edge-Colored Graphs

   • Eric Angel, Evripidis Bampis, Alexander Kononov, Dimitris Paparas, Emmanouil Pountourakis, Vassilis Zissimopoulos

   Pages 50-61

9. How to Pack Your Items When You Have to Buy Your Knapsack

   • Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott, José Verschae

   Pages 62-73

10. Computing Behavioral Distances, Compositionally

    • Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare

    Pages 74-85

11. Which Finitely Ambiguous Automata Recognize Finitely Sequential Functions?

    • Sebastian Bala

    Pages 86-97

12. Rewriting Guarded Negation Queries

    • Vince Bárány, Michael Benedikt, Balder ten Cate

    Pages 98-110

13. Parity Games and Propositional Proofs

    • Arnold Beckmann, Pavel Pudlák, Neil Thapen

    Pages 111-122

14. Logic and Branching Automata

    • Nicolas Bedon

    Pages 123-134

15. A Constant Factor Approximation for the Generalized Assignment Problem with Minimum Quantities and Unit Size Items

    • Marco Bender, Clemens Thielen, Stephan Westphal

    Pages 135-145

16. Determinacy and Rewriting of Top-Down and MSO Tree Transformations

    • Michael Benedikt, Joost Engelfriet, Sebastian Maneth

    Pages 146-158

17. On the Speed of Constraint Propagation and the Time Complexity of Arc Consistency Testing

    • Christoph Berkholz, Oleg Verbitsky

    Pages 159-170

18. Validity of Tree Pattern Queries with Respect to Schema Information

    • Henrik Björklund, Wim Martens, Thomas Schwentick

    Pages 171-182

19. Auctions for Partial Heterogeneous Preferences

    • Piero A. Bonatti, Marco Faella, Clemente Galdi, Luigi Sauro

    Pages 183-194

20. New Polynomial Cases of the Weighted Efficient Domination Problem

    • Andreas Brandstädt, Martin Milanič, Ragnar Nevries

    Pages 195-206

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.

• approximation algorithms
• finite automata
• proof complexity
• satisfiability
• temporal logic
• algorithm analysis and problem complexity
• data structures

• Institute for Science and Technology, Klosterneuburg, Austria

  Krishnendu Chatterjee

• Charles University, Prague, Czech Republic

  Jirí Sgall

Policies and ethics