FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science

Invited Papers.- Shared-Variable Concurrency: A Proposal.- Hennessy-Plotkin-Brookes Revisited.- Approximation Algorithms for 2-Stage Stochastic Optimization Problems.- The Number of Crossing Free Configurations on Finite Point Sets in the Plane.- Contributed Papers – Track A.- Normal and Feature Approximations from Noisy Point Clouds.- Coresets for Discrete Integration and Clustering.- Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time.- One-Input-Face MPCVP Is Hard for L, But in LogDCFL.- Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs.- Multi-stack Boundary Labeling Problems.- Computing a Center-Transversal Line.- On Obtaining Pseudorandomness from Error-Correcting Codes.- Fast Edge Colorings with Fixed Number of Colors to Minimize Imbalance.- Zero Error List-Decoding Capacity of the q/(q–1) Channel.- Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems.- Solving Connected Dominating Set Faster Than 2 n .- Linear-Time Algorithms for Two Subtree-Comparison Problems on Phylogenetic Trees with Different Species.- Computationally Sound Symbolic Secrecy in the Presence of Hash Functions.- Some Results on Average-Case Hardness Within the Polynomial Hierarchy.- Unbiased Rounding of Rational Matrices.- Contributed Papers – Track B.- Rational Behaviour and Strategy Construction in Infinite Multiplayer Games.- The Anatomy of Innocence Revisited.- Testing Probabilistic Equivalence Through Reinforcement Learning.- On Decidability of LTL Model Checking for Process Rewrite Systems.- Monitoring of Real-Time Properties.- A Proof System for the Linear Time ?-Calculus.- Tree Automata Make Ordinal Theory Easy.- Context-Sensitive Dependency Pairs.- On Reduction Criteria for Probabilistic Reward Models.- Distributed Synthesis for Well-Connected Architectures.- The Meaning of Ordered SOS.- Almost Optimal Strategies in One Clock Priced Timed Games.- Expressivity Properties of Boolean BI Through Relational Models.- On Continuous Timed Automata with Input-Determined Guards.- Safely Freezing LTL.- Branching Pushdown Tree Automata.- Validity Checking for Finite Automata over Linear Arithmetic Constraints.- Game Semantics for Higher-Order Concurrency.