FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science: 20th Conference New Delhi, India, December 13–15, 2000 Proceedings

Model Checking: Theory into Practice....Pages 1-10
An Algebra for XML Query....Pages 11-45
Irregularities of Distribution, Derandomization, and Complexity Theory....Pages 46-54
Rewriting Logic as a Metalogical Framework....Pages 55-80
Frequency Assignment in Mobile Phone Systems....Pages 81-86
Data Provenance: Some Basic Issues....Pages 87-93
Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and Its Connections with Principal Partition....Pages 94-105
On-Line Edge-Coloring with a Fixed Number of Colors....Pages 106-116
On Approximability of the Independent/Connected Edge Dominating Set Problems....Pages 117-126
Model Checking CTL Properties of Pushdown Systems....Pages 127-138
A Decidable Dense Branching-Time Temporal Logic....Pages 139-150
Fair Equivalence Relations....Pages 151-163
Arithmetic Circuits and Polynomial Replacement Systems....Pages 164-175
The Bounded Weak Monadic Quantifier Alternation Hierarchy of Equational Graphs Is Infinite....Pages 176-187
Combining Semantics with Non-standard Interpreter Hierarchies....Pages 188-200
Using Modes to Ensure Subject Reduction for Typed Logic Programs with Subtyping....Pages 201-213
Dynamically Ordered Probabilistic Choice Logic Programming....Pages 214-226
Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems....Pages 227-239
Planar Graph Blocking for External Searching....Pages 240-251
A Complete Fragment of Higher-Order Duration μ-Calculus....Pages 252-263
A Complete Axiomatisation for Timed Automata....Pages 264-276
Text Sparsification via Local Maxima....Pages 277-289
Approximate Swapped Matching....Pages 290-301
A Semantic Theory for Heterogeneous System Design....Pages 302-311
Formal Verification of the Ricart-Agrawala Algorithm....Pages 312-324
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation....Pages 325-335
Is the Standard Proof System for SAT P-Optimal?....Pages 336-347
A General Framework for Types in Graph Rewriting....Pages 348-360
The Ground Congruence for Chi Calculus....Pages 361-372
Inheritance in the Join Calculus....Pages 373-384
Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints....Pages 385-396
Dynamic Spectrum Allocation: The Impotency of Duration Notification....Pages 397-408
The Fine Structure of Game Lambda Models....Pages 409-420
Strong Normalization of Second Order Symmetric λ-Calculus....Pages 421-428
Scheduling to Minimize the Average Completion Time of Dedicated Tasks....Pages 429-441
Hunting for Functionally Analogous Genes....Pages 442-453
Keeping Track of the Latest Gossip in Shared Memory Systems....Pages 454-464
Concurrent Knowledge and Logical Clock Abstractions....Pages 465-476
Decidable Hierarchies of Starfree Languages....Pages 477-488
Prefix Languages of Church-Rosser Languages....Pages 489-502
....Pages 503-515