Mathematical Foundations of Computer Science 2009

- Invited Papers
- Four Subareas of the Theory of Constraints, and Their Links
- Synchronization of Regular Automata
- Stochastic Process Creation
- Stochastic Games with Finitary Objectives
- Stochastic Data Streams
- Recent Advances in Population Protocols
- How to Sort a Train
- Contributed Papers
- Arithmetic Circuits, Monomial Algebras and Finite Automata
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Energy-Efficient Communication in Multi-interface Wireless Networks
- Private Capacities in Mechanism Design
- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
- Sampling Edge Covers in 3-Regular Graphs
- Balanced Paths in Colored Graphs
- Few Product Gates But Many Zeros
- Branching Programs for Tree Evaluation
- A Dichotomy Theorem for Polynomial Evaluation
- DP-Complete Problems Derived from Extremal NP-Complete Properties
- The Synchronization Problem for Locally Strongly Transitive Automata
- Constructing Brambles
- Self-indexed Text Compression Using Straight-Line Programs
- Security and Tradeoffs of the Akl-Taylor Scheme and Its Variants
- Parameterized Complexity Classes under Logical Reductions
- The Communication Complexity of Non-signaling Distributions
- How to Use Spanning Trees to Navigate in Graphs
- Representing Groups on Graphs
- Admissible Strategies in Infinite Games over Graphs
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
- Future-Looking Logics on Data Words and Trees
- A By-Level Analysis of Multiplicative Exponential Linear Logic
- Hyper-minimisation Made Efficient
- Regular Expressions with Counting: Weak versus Strong Determinism
- Choosability of P 5-Free Graphs
- Time-Bounded Kolmogorov Complexity and Solovay Functions
- The Longest Path Problem Is Polynomial on Interval Graphs
- Synthesis for Structure Rewriting Systems
- On the Hybrid Extension of CTL and CTL?+?
- Bounds on Non-surjective