Constitutes the refereed proceedings of the 26th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2006, held in Kolkata, India, in December 2006.

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 Criteriafor 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.

GPSR Compliance The European Union's (EU) General Product Safety Regulation (GPSR) is a set of rules that requires consumer products to be safe and our obligations to ensure this. If you have any concerns about our products you can contact us on ProductSafety@springernature.com. In case Publisher is established outside the EU, the EU authorized representative is: Springer Nature Customer Service Center GmbH Europaplatz 3 69115 Heidelberg, Germany ProductSafety@springernature.com