20. FSTTCS 2000: New Delhi, India

Invited Presentations

• E. Allen Emerson:
  Model Checking: Theory into Practice. 1-10
  
• Mary F. Fernández, Jérôme Siméon, Philip Wadler:
  An Algebra for XML Query. 11-45
  
• Bernard Chazelle:
  Irregularities of Distribution, Derandomization, and Complexity Theory. 46-54
  
• David A. Basin, Manuel Clavel, José Meseguer:
  Rewriting Logic as a Metalogical Framework. 55-80
  
• Martin Grötschel:
  Frequency Assignment in Mobile Phone Systems. 81-86
  
• Peter Buneman, Sanjeev Khanna, Wang Chiew Tan:
  Data Provenance: Some Basic Issues. 87-93
  

Contributions

• Sachin B. Patkar, H. Narayanan:
  Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and Its Connections with Principal Partition. 94-105
  
• Lene M. Favrholdt, Morten N. Nielsen:
  On-Line Edge-Coloring with a Fixed Number of Colors. 106-116
  
• Toshihiro Fujito:
  On Approximability of the Independent/Connected Edge Dominating Set Problems. 117-126
  
• Igor Walukiewicz:
  Model Checking CTL Properties of Pushdown Systems. 127-138
  
• Salvatore La Torre, Margherita Napoli:
  A Decidable Dense Branching-Time Temporal Logic. 139-150
  
• Orna Kupferman, Nir Piterman, Moshe Y. Vardi:
  Fair Equivalence Relations. 151-163
  
• Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner:
  Arithmetic Circuits and Polynomial Replacement Systems. 164-175
  
• Jaikumar Radhakrishnan, Pranab Sen, Sundar Vishwanathan:
  Depth-3 Arithmetic Circuits for S_n²(X) and Extensions of the Graham-Pollack Theorem. 176-187
  
• Olivier Ly:
  The Bounded Weak Monadic Quantifier Alternation Hierarchy of Equational Graphs Is Infinite. 188-200
  
• Sergei M. Abramov, Robert Glück:
  Combining Semantics with Non-standard Interpreter Hierarchies. 201-213
  
• Jan-Georg Smaus, François Fages, Pierre Deransart:
  Using Modes to Ensure Subject Reduction for Typed Logic Programs with Subtyping. 214-226
  
• Marina De Vos, Dirk Vermeir:
  Dynamically Ordered Probabilistic Choice Logic Programming. 227-239
  
• Michael R. Fellows, Catherine McCartin, Frances A. Rosamond, Ulrike Stege:
  Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems. 240-251
  
• Surender Baswana, Sandeep Sen:
  Planar Graph Blocking for External Searching. 252-263
  
• Dimitar P. Guelev:
  A Complete Fragment of Higher-Order Duration µ-Calculus. 264-276
  
• Huimin Lin, Wang Yi:
  A Complete Axiomatisation for Timed Automata. 277-289
  
• Pierluigi Crescenzi, Alberto Del Lungo, Roberto Grossi, Elena Lodi, Linda Pagli, Gianluca Rossi:
  Text Sparsification via Local Maxima. 290-301
  
• Amihood Amir, Moshe Lewenstein, Ely Porat:
  Approximate Swapped Matching. 302-311
  
• Rance Cleaveland, Gerald Lüttgen:
  A Semantic Theory for Heterogeneous System Design. 312-324
  
• Ekaterina Sedletsky, Amir Pnueli, Mordechai Ben-Ari:
  Formal Verification of the Ricart-Agrawala Algorithm. 325-335
  
• Johannes Köbler, Wolfgang Lindner:
  On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation. 336-347
  
• Holger Spakowski, Jörg Vogel:
  Theta₂^p-Completeness: A Classical Approach for New Results. 348-360
  
• Johannes Köbler, Jochen Messner:
  Is the Standard Proof System for SAT P-Optimal? 361-372
  
• Barbara König:
  A General Framework for Types in Graph Rewriting. 373-384
  
• Yuxi Fu, Zhenrong Yang:
  The Ground Congruence for Chi Calculus. 385-396
  
• Cédric Fournet, Cosimo Laneve, Luc Maranget, Didier Rémy:
  Inheritance in the Join Calculus. 397-408
  
• Stefano Leonardi, Alberto Marchetti-Spaccamela, Andrea Vitaletti:
  Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints. 409-420
  
• Bala Kalyanasundaram, Kirk Pruhs:
  Dynamic Spectrum Allocation: The Impotency of Duration Notification. 421-428
  
• Pietro Di Gianantonio, Gianluca Franco:
  The Fine Structure of Game Lambda Models. 429-441
  
• Michel Parigot:
  Strong Normalization of Second Order Symmetric lambda-Calculus. 442-453
  
• Foto N. Afrati, Evripidis Bampis, Aleksei V. Fishkin, Klaus Jansen, Claire Kenyon:
  Scheduling to Minimize the Average Completion Time of Dedicated Tasks. 454-464
  
• Michael T. Hallett, Jens Lagergren:
  Hunting for Functionally Analogous Genes. 465-476
  
• Bharat Adsul, Aranyak Mehta, Milind A. Sohoni:
  Keeping Track of the Latest Gossip in Shared Memory Systems. 477-488
  
• Ajay D. Kshemkalyani:
  Concurrent Knowledge and Logical Clock Abstractions. 489-502
  
• Christian Glaßer, Heinz Schmitz:
  Decidable Hierarchies of Starfree Languages. 503-515
  
• Jens R. Woinowski:
  Prefix Languages of Church-Rosser Languages. 516-530