FST TCS 2000: Foundations of Software Technology and Theoretical Science

This book constitutes the refereed proceedings of the 20th international Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2000, held in New Delhi, India in December 2000. The 36 revised full papers presented were carefully reviewed and selected from a total of 141 submissions; also included are six invited papers. The volume provides broad coverage of the logical and mathematical foundations of computer science and spans the whole range of theoretical computer science.

Inhalt

Invited Presentations.- Model Checking: Theory into Practice.- An Algebra for XML Query.- Irregularities of Distribution, Derandomization, and Complexity Theory.- Rewriting Logic as a Metalogical Framework.- Frequency Assignment in Mobile Phone Systems.- Data Provenance: Some Basic Issues.- Contributions.- Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and Its Connections with Principal Partition.- On-Line Edge-Coloring with a Fixed Number of Colors.- On Approximability of the Independent/Connected Edge Dominating Set Problems.- Model Checking CTL Properties of Pushdown Systems.- A Decidable Dense Branching-Time Temporal Logic.- Fair Equivalence Relations.- Arithmetic Circuits and Polynomial Replacement Systems.- Depth-3 Arithmetic Circuits for S inn su2 (X) and Extensions of the Graham-Pollack Theorem.- The Bounded Weak Monadic Quantifier Alternation Hierarchy of Equational Graphs Is Infinite.- Combining Semantics with Non-standard Interpreter Hierarchies.- Using Modes to Ensure Subject Reduction for Typed Logic Programs with Subtyping.- Dynamically Ordered Probabilistic Choice Logic Programming.- Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems.- Planar Graph Blocking for External Searching.- A Complete Fragment of Higher-Order Duration ?-Calculus.- A Complete Axiomatisation for Timed Automata.- Text Sparsification via Local Maxima.- Approximate Swapped Matching.- A Semantic Theory for Heterogeneous System Design.- Formal Verification of the Ricart-Agrawala Algorithm.- On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation.- ? in2 sup -Completeness: A Classical Approach for New Results.- Is the Standard Proof System for SAT P-Optimal?.- A General Framework for Types in Graph Rewriting.- The Ground Congruence for Chi Calculus.- Inheritance in the Join Calculus.- Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints.- Dynamic Spectrum Allocation: The Impotency of Duration Notification.- The Fine Structure of Game Lambda Models.- Strong Normalization of Second Order Symmetric ?-Calculus.- Scheduling to Minimize the Average Completion Time of Dedicated Tasks.- Hunting for Functionally Analogous Genes.- Keeping Track of the Latest Gossip in Shared Memory Systems.- Concurrent Knowledge and Logical Clock Abstractions.- Decidable Hierarchies of Starfree Languages.- Prefix Languages of Church-Rosser Languages.