Ebook: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science: 25th International Conference, Hyderabad, India, December 15-18, 2005. Proceedings

This book constitutes the refereed proceedings of the 25th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2005, held in Hyderabad, India, in December 2005.

The 38 revised full papers presented together with 7 invited papers were carefully reviewed and selected from 167 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.

---

This book constitutes the refereed proceedings of the 25th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2005, held in Hyderabad, India, in December 2005.

The 38 revised full papers presented together with 7 invited papers were carefully reviewed and selected from 167 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.

Content:
Front Matter....Pages -
Semiperfect-Information Games....Pages 1-18
Computational Complexity Since 1980....Pages 19-47
Developments in Data Structure Research During the First 25 Years of FSTTCS....Pages 48-59
Inference Systems for Logical Algorithms....Pages 60-78
From Logic to Games....Pages 79-91
Proving Lower Bounds Via Pseudo-random Generators....Pages 92-105
Erd?s Magic....Pages 106-106
No Coreset, No Cry: II....Pages 107-115
Improved Bounds on the Union Complexity of Fat Objects....Pages 116-127
On the Bisimulation Congruence in ?-Calculus....Pages 128-139
Extending Howe’s Method to Early Bisimulations for Typed Mobile Embedded Resources with Local Names....Pages 140-151
Approximation Algorithms for Wavelength Assignment....Pages 152-163
The Set Cover with Pairs Problem....Pages 164-176
Non-disclosure for Distributed Mobile Code....Pages 177-188
Quantitative Models and Implicit Complexity....Pages 189-200
The MSO Theory of Connectedly Communicating Processes....Pages 201-212
Reachability of Hennessy-Milner Properties for Weakly Extended PRS....Pages 213-224
Decision Procedures for Queues with Integer Constraints....Pages 225-237
The Directed Planar Reachability Problem....Pages 238-249
Dimensions of Copeland-Erd?s Sequences....Pages 250-260
Refining the Undecidability Frontier of Hybrid Automata....Pages 261-272
When Are Timed Automata Weakly Timed Bisimilar to Time Petri Nets?....Pages 273-284
Subquadratic Algorithms for Workload-Aware Haar Wavelet Synopses....Pages 285-296
Practical Algorithms for Tracking Database Join Sizes....Pages 297-309
On Sampled Semantics of Timed Systems....Pages 310-321
Eventual Timed Automata....Pages 322-334
Causal Closure for MSC Languages....Pages 335-347
Reachability Analysis of Multithreaded Software with Asynchronous Communication....Pages 348-359
Probabilistic Analysis for a Multiple Depot Vehicle Routing Problem....Pages 360-371
Computing the Expected Accumulated Reward and Gain for a Subclass of Infinite Markov Chains....Pages 372-383
Towards a CTL* Tableau....Pages 384-395
Bisimulation Quantified Logics: Undecidability....Pages 396-407
Logarithmic-Time Single Deleter, Multiple Inserter Wait-Free Queues and Stacks....Pages 408-419
Monitoring Stable Properties in Dynamic Peer-to-Peer Distributed Systems....Pages 420-431
Modal Strength Reduction in Quantified Discrete Duration Calculus....Pages 432-443
Comparing Trees Via Crossing Minimization....Pages 444-456
On Counting the Number of Consistent Genotype Assignments for Pedigrees....Pages 457-469
Fixpoint Logics on Hierarchical Structures....Pages 470-482
The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable....Pages 483-494
Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation....Pages 495-504
Testing Concurrent Systems: An Interpretation of Intuitionistic Logic....Pages 505-516
Proofs of Termination of Rewrite Systems for Polytime Functions....Pages 517-528
On the Controller Synthesis for Finite-State Markov Decision Processes....Pages 529-540
Reasoning About Quantum Knowledge....Pages 541-552
Back Matter....Pages 553-564
....Pages -