This book 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.
The 34 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 155 submissions. A broad variety of current topics from the theory of computing are addressed, ranging from software science, programming theory, systems design and analysis, formal methods, mathematical logic, mathematical foundations, discrete mathematics, combinatorial mathematics, complexity theory, and automata theory to theoretical computer science in general.
Author(s): Gérard Boudol (auth.), S. Arun-Kumar, Naveen Garg (eds.)
Series: Lecture Notes in Computer Science 4337 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2006
Language: English
Pages: 434
Tags: Logics and Meanings of Programs; Programming Languages, Compilers, Interpreters; Mathematical Logic and Formal Languages; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Discrete Mathematics in Computer Scienc
Front Matter....Pages -
Shared-Variable Concurrency: A Proposal....Pages 1-3
Hennessy-Plotkin-Brookes Revisited....Pages 4-4
Approximation Algorithms for 2-Stage Stochastic Optimization Problems....Pages 5-19
The Number of Crossing Free Configurations on Finite Point Sets in the Plane....Pages 20-20
Normal and Feature Approximations from Noisy Point Clouds....Pages 21-32
Coresets for Discrete Integration and Clustering....Pages 33-44
Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time....Pages 45-56
One-Input-Face MPCVP Is Hard for L, But in LogDCFL....Pages 57-68
Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs....Pages 69-80
Multi-stack Boundary Labeling Problems....Pages 81-92
Computing a Center-Transversal Line....Pages 93-104
On Obtaining Pseudorandomness from Error-Correcting Codes....Pages 105-116
Fast Edge Colorings with Fixed Number of Colors to Minimize Imbalance....Pages 117-128
Zero Error List-Decoding Capacity of the q /( q –1) Channel....Pages 129-138
Fast Exponential Algorithms for Maximum r -Regular Induced Subgraph Problems....Pages 139-151
Solving Connected Dominating Set Faster Than 2 n ....Pages 152-163
Linear-Time Algorithms for Two Subtree-Comparison Problems on Phylogenetic Trees with Different Species....Pages 164-175
Computationally Sound Symbolic Secrecy in the Presence of Hash Functions....Pages 176-187
Some Results on Average-Case Hardness Within the Polynomial Hierarchy....Pages 188-199
Unbiased Rounding of Rational Matrices....Pages 200-211
Rational Behaviour and Strategy Construction in Infinite Multiplayer Games....Pages 212-223
The Anatomy of Innocence Revisited....Pages 224-235
Testing Probabilistic Equivalence Through Reinforcement Learning....Pages 236-247
On Decidability of LTL Model Checking for Process Rewrite Systems....Pages 248-259
Monitoring of Real-Time Properties....Pages 260-272
A Proof System for the Linear Time μ -Calculus....Pages 273-284
Tree Automata Make Ordinal Theory Easy....Pages 285-296
Context-Sensitive Dependency Pairs....Pages 297-308
On Reduction Criteria for Probabilistic Reward Models....Pages 309-320
Distributed Synthesis for Well-Connected Architectures....Pages 321-332
The Meaning of Ordered SOS....Pages 333-344
Almost Optimal Strategies in One Clock Priced Timed Games....Pages 345-356
Expressivity Properties of Boolean BI Through Relational Models....Pages 357-368
On Continuous Timed Automata with Input-Determined Guards....Pages 369-380
Safely Freezing LTL....Pages 381-392
Branching Pushdown Tree Automata....Pages 393-404
Validity Checking for Finite Automata over Linear Arithmetic Constraints....Pages 405-416
Game Semantics for Higher-Order Concurrency....Pages 417-428
Back Matter....Pages -
