Mathematical Foundations of Computer Science 2011

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Nearest Neighbor Search in High-Dimensional Spaces
3. Altmetric Badge
   Chapter 2 Invariantization of Listings
4. Altmetric Badge
   Chapter 3 Duality and Recognition
5. Altmetric Badge
   Chapter 4 Some Variants of the Star Height Problem
6. Altmetric Badge
   Chapter 5 Generic Techniques to Round SDP Relaxations
7. Altmetric Badge
   Chapter 6 New Proofs in Graph Minors
8. Altmetric Badge
   Chapter 7 The Least-Core of Threshold Network Flow Games
9. Altmetric Badge
   Chapter 8 Adhesivity Is Not Enough: Local Church-Rosser Revisited
10. Altmetric Badge
    Chapter 9 Quantitative Refinement for Weighted Modal Transition Systems
11. Altmetric Badge
    Chapter 10 Faster Coupon Collecting via Replication with Applications in Gossiping
12. Altmetric Badge
    Chapter 11 Verifying Proofs in Constant Depth
13. Altmetric Badge
    Chapter 12 The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree
14. Altmetric Badge
    Chapter 13 Model Checking Coverability Graphs of Vector Addition Systems
15. Altmetric Badge
    Chapter 14 Hard Functions for Low-Degree Polynomials over Prime Fields
16. Altmetric Badge
    Chapter 15 Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking
17. Altmetric Badge
    Chapter 16 The Reachability Problem for Vector Addition System with One Zero-Test
18. Altmetric Badge
    Chapter 17 The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed Complexity
19. Altmetric Badge
    Chapter 18 Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains
20. Altmetric Badge
    Chapter 19 Pattern-Guided Data Anonymization and Clustering
21. Altmetric Badge
    Chapter 20 Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL -Complete
22. Altmetric Badge
    Chapter 21 Energy and Mean-Payoff Parity Markov Decision Processes
23. Altmetric Badge
    Chapter 22 The Role of Polymorphism in the Characterisation of Complexity by Soft Types
24. Altmetric Badge
    Chapter 23 An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
25. Altmetric Badge
    Chapter 24 On the Use of Guards for Logics with Data
26. Altmetric Badge
    Chapter 25 An Elementary Proof of a 3 n  −  o ( n ) Lower Bound on the Circuit Complexity of Affine Dispersers
27. Altmetric Badge
    Chapter 26 On the Complexity of the l -diversity Problem
28. Altmetric Badge
    Chapter 27 Infinite Synchronizing Words for Probabilistic Automata
29. Altmetric Badge
    Chapter 28 Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs
30. Altmetric Badge
    Chapter 29 Parity Games on Graphs with Medium Tree-Width
31. Altmetric Badge
    Chapter 30 Satisfiability of Systems of Equations of Real Analytic Functions Is Quasi-decidable
32. Altmetric Badge
    Chapter 31 On Minimising Automata with Errors
33. Altmetric Badge
    Chapter 32 Contracting a Chordal Graph to a Split Graph or a Tree
34. Altmetric Badge
    Chapter 33 Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
35. Altmetric Badge
    Chapter 34 A Universally Defined Undecidable Unimodal Logic
36. Altmetric Badge
    Chapter 35 On the Approximability of Minimum Topic Connected Overlay and Its Special Instances
37. Altmetric Badge
    Chapter 36 Can Everybody Sit Closer to Their Friends Than Their Enemies?
38. Altmetric Badge
    Chapter 37 Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
39. Altmetric Badge
    Chapter 38 Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions
40. Altmetric Badge
    Chapter 39 Size and Computation of Injective Tree Automatic Presentations
41. Altmetric Badge
    Chapter 40 Symmetric Functions Capture General Functions
42. Altmetric Badge
    Chapter 41 Compressed Word Problems for Inverse Monoids
43. Altmetric Badge
    Chapter 42 Pushing for Weighted Tree Automata
44. Altmetric Badge
    Chapter 43 Periodicity Algorithms for Partial Words
45. Altmetric Badge
    Chapter 44 State Complexity of Operations on Input-Driven Pushdown Automata
46. Altmetric Badge
    Chapter 45 Conflict Packing Yields Linear Vertex-Kernels for k -FAST , k -dense RTI and a Related Problem
47. Altmetric Badge
    Chapter 46 Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence
48. Altmetric Badge
    Chapter 47 Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
49. Altmetric Badge
    Chapter 48 Distributed Synthesis for Regular and Contextfree Specifications
50. Altmetric Badge
    Chapter 49 Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols
51. Altmetric Badge
    Chapter 50 Untimed Language Preservation in Timed Systems
52. Altmetric Badge
    Chapter 51 Lower Bounds for Linear Decision Trees via an Energy Complexity Argument
53. Altmetric Badge
    Chapter 52 Weak Cost Monadic Logic over Infinite Trees
54. Altmetric Badge
    Chapter 53 Linear Problem Kernels for Planar Graph Problems with Small Distance Property
55. Altmetric Badge
    Chapter 54 New Parameterized Algorithms for the Edge Dominating Set Problem