Mathematical Foundations of Computer Science 2009

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Four Subareas of the Theory of Constraints, and Their Links
3. Altmetric Badge
   Chapter 2 Synchronization of Regular Automata
4. Altmetric Badge
   Chapter 3 Stochastic Process Creation
5. Altmetric Badge
   Chapter 4 Stochastic Games with Finitary Objectives
6. Altmetric Badge
   Chapter 5 Stochastic Data Streams
7. Altmetric Badge
   Chapter 6 Recent Advances in Population Protocols
8. Altmetric Badge
   Chapter 7 How to Sort a Train
9. Altmetric Badge
   Chapter 8 Arithmetic Circuits, Monomial Algebras and Finite Automata
10. Altmetric Badge
    Chapter 9 An Improved Approximation Bound for Spanning Star Forest and Color Saving
11. Altmetric Badge
    Chapter 10 Energy-Efficient Communication in Multi-interface Wireless Networks
12. Altmetric Badge
    Chapter 11 Private Capacities in Mechanism Design
13. Altmetric Badge
    Chapter 12 Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
14. Altmetric Badge
    Chapter 13 Sampling Edge Covers in 3-Regular Graphs
15. Altmetric Badge
    Chapter 14 Balanced Paths in Colored Graphs
16. Altmetric Badge
    Chapter 15 Few Product Gates But Many Zeros
17. Altmetric Badge
    Chapter 16 Branching Programs for Tree Evaluation
18. Altmetric Badge
    Chapter 17 A Dichotomy Theorem for Polynomial Evaluation
19. Altmetric Badge
    Chapter 18 DP-Complete Problems Derived from Extremal NP-Complete Properties
20. Altmetric Badge
    Chapter 19 The Synchronization Problem for Locally Strongly Transitive Automata
21. Altmetric Badge
    Chapter 20 Constructing Brambles
22. Altmetric Badge
    Chapter 21 Self-indexed Text Compression Using Straight-Line Programs
23. Altmetric Badge
    Chapter 22 Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants
24. Altmetric Badge
    Chapter 23 Parameterized Complexity Classes under Logical Reductions
25. Altmetric Badge
    Chapter 24 The Communication Complexity of Non-signaling Distributions
26. Altmetric Badge
    Chapter 25 How to Use Spanning Trees to Navigate in Graphs
27. Altmetric Badge
    Chapter 26 Representing Groups on Graphs
28. Altmetric Badge
    Chapter 27 Admissible Strategies in Infinite Games over Graphs
29. Altmetric Badge
    Chapter 28 A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
30. Altmetric Badge
    Chapter 29 Future-Looking Logics on Data Words and Trees
31. Altmetric Badge
    Chapter 30 A By-Level Analysis of Multiplicative Exponential Linear Logic
32. Altmetric Badge
    Chapter 31 Hyper-minimisation Made Efficient
33. Altmetric Badge
    Chapter 32 Regular Expressions with Counting: Weak versus Strong Determinism
34. Altmetric Badge
    Chapter 33 Choosability of P 5 -Free Graphs
35. Altmetric Badge
    Chapter 34 Time-Bounded Kolmogorov Complexity and Solovay Functions
36. Altmetric Badge
    Chapter 35 The Longest Path Problem Is Polynomial on Interval Graphs
37. Altmetric Badge
    Chapter 36 Synthesis for Structure Rewriting Systems
38. Altmetric Badge
    Chapter 37 On the Hybrid Extension of CTL and CTL  + 
39. Altmetric Badge
    Chapter 38 Bounds on Non-surjective Cellular Automata
40. Altmetric Badge
    Chapter 39 FO Model Checking on Nested Pushdown Trees
41. Altmetric Badge
    Chapter 40 The Prismoid of Resources
42. Altmetric Badge
    Chapter 41 A Dynamic Algorithm for Reachability Games Played on Trees
43. Altmetric Badge
    Chapter 42 An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable
44. Altmetric Badge
    Chapter 43 Graph Decomposition for Improving Memoryless Periodic Exploration
45. Altmetric Badge
    Chapter 44 On FO 2 Quantifier Alternation over Words
46. Altmetric Badge
    Chapter 45 On the Recognizability of Self-generating Sets
47. Altmetric Badge
    Chapter 46 The Isomorphism Problem for k -Trees Is Complete for Logspace
48. Altmetric Badge
    Chapter 47 Snake-Deterministic Tiling Systems
49. Altmetric Badge
    Chapter 48 Query Automata for Nested Words
50. Altmetric Badge
    Chapter 49 A General Class of Models of $\mathcal{H}^*$
51. Altmetric Badge
    Chapter 50 The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I
52. Altmetric Badge
    Chapter 51 Colouring Non-sparse Random Intersection Graphs
53. Altmetric Badge
    Chapter 52 On the Structure of Optimal Greedy Computation (for Job Scheduling)
54. Altmetric Badge
    Chapter 53 A Probabilistic PTAS for Shortest Common Superstring
55. Altmetric Badge
    Chapter 54 The Cost of Stability in Network Flow Games
56. Altmetric Badge
    Chapter 55 (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata
57. Altmetric Badge
    Chapter 56 Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm
58. Altmetric Badge
    Chapter 57 From Parity and Payoff Games to Linear Programming
59. Altmetric Badge
    Chapter 58 Partial Randomness and Dimension of Recursively Enumerable Reals
60. Altmetric Badge
    Chapter 59 Partial Solution and Entropy
61. Altmetric Badge
    Chapter 60 On Pebble Automata for Data Languages with Decidable Emptiness Problem
62. Altmetric Badge
    Chapter 61 Size and Energy of Threshold Circuits Computing Mod Functions
63. Altmetric Badge
    Chapter 62 Points on Computable Curves of Computable Lengths
64. Altmetric Badge
    Chapter 63 The Expressive Power of Binary Submodular Functions