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.
Author(s): Krishnendu Chatterjee, Thomas A. Henzinger (auth.), Sundar Sarukkai, Sandeep Sen (eds.)
Series: Lecture Notes in Computer Science 3821 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2005
Language: English
Pages: 566
Tags: Logics and Meanings of Programs; Programming Languages, Compilers, Interpreters; Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Mathematical Logic and Formal Languages; Discrete Mathematics in Computer Scienc
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
On the Expressiveness of TPTL and MTL ....Pages 432-443
Modal Strength Reduction in Quantified Discrete Duration Calculus....Pages 444-456
Comparing Trees Via Crossing Minimization....Pages 457-469
On Counting the Number of Consistent Genotype Assignments for Pedigrees....Pages 470-482
Fixpoint Logics on Hierarchical Structures....Pages 483-494
The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable....Pages 495-504
Market Equilibrium for CES Exchange Economies: Existence, Multiplicity, and Computation....Pages 505-516
Testing Concurrent Systems: An Interpretation of Intuitionistic Logic....Pages 517-528
Proofs of Termination of Rewrite Systems for Polytime Functions....Pages 529-540
On the Controller Synthesis for Finite-State Markov Decision Processes....Pages 541-552
Reasoning About Quantum Knowledge....Pages 553-564
Back Matter....Pages -
