******************************************************************* * * * Call for Participation * * * * Foundations of Software Technology * * and * * Theoretical Computer Science * * (FST TCS 2000) * * * * India International Centre * * New Delhi, India * * 13--15 December July, 2000 * * * * REGISTER AT http://www.cse.iitd.ernet.in~/fsttcs20 * * EARLY REGISTRATION DEADLINE IS November 15 * * * ******************************************************************* Invited Speakers: Peter Buneman (U Penn) Bernard Chazelle (Princeton) E. Allen Emerson (U Texas, Austin) Martin Groetschel (ZIB, Berlin) Jose Meseguer (SRI) Philip Wadler (Avaya Labs Satellite Events: Tutorial Workshop on Recent Advances in Programming Languages December 11-12, 2000 at IIT Delhi, Hauz Khas Workshop on Geometry December 16-17, 2000 at IIT Delhi, Hauz Khas FST TCS 2000 Preliminary Programme 13 December 2000 9:00-9:30 Opening 9:30-10:30 Invited Talk: E Allen Emerson Model Checking: Theory into Practice 10:30-11:00 Tea 11:00-12:30 40. Fast On-line/Off-line 100. Model checking CTL Algorithms for Optimal Properties of Pushdown Systems Reinforcement of a Network Igor Walukiewicz and its Connections with Principal Partition H. Narayanan, Sachin B. Patkar 59. On-Line Edge-Coloring 125. A Decidable Dense with a Fixed Number of Colors Branching-time Temporal Logic Lene Monrad Favrholdt, Salvatore La Torre and Morten Nyhave Nielsen Margherita Napoli 15. On Approximability of the 126. Fair Equivalence Relations Independent/Connected Edge Orna Kupferman, Nir Piterman, Dominating Set Problems Moshe Vardi Toshihiro Fujito 12:30-14:00 Lunch 14:00-15:00 Invited Talk: Philip Wadler An Algebra for XML Query 15:00-15:30 Tea 15:30-17:00 8. Arithmetic Circuits and 113. Combining Semantics with Polynomial Replacement Systems Non-Standard Interpreter Pierre McKenzie, Heribert Hierarchies Vollmer, Klaus W. Wagner Sergei Abramov, Robert Glueck 70. Depth-3 Arithmetic Circuits 112. Using Modes to Ensure for S(2,n)(X) and Extensions of Subject Reduction for Typed the Graham-Pollack Theorem Logic Programs with Subtyping Jaikumar Radhakrishnan, Pranab Jan-Georg Smaus, Francois Sen, Sundar Vishwanathan Fages, Pierre Deransart 130. The Weak Monadic Quantifier 23. Dynamically Ordered Alternation Hierarchy of Probabilistic Choice Logic Equational Graphs is Infinite Programming Ly Olivier Marina De Vos, Dirk Vermeir 14 December 2000 9:00-10:00 Invited Talk: Bernard Chazelle Irregularities of Distribution, Derandomization, and Complexity Theory 10:10-11:10 147. Coordinatized Kernels and Catalytic Reductions: Improved 12. A Complete Fragment of FPT Algorithms for Max Leaf Higher-Order Duration Spanning Tree and Other Problems $\mu$-Calculus Michael R. Fellows, Catherine Dimitar P. Guelev McCartin, Ulrike Stege, Frances A. Rosamond 53. Planar Graph Blocking for 39. A Complete Axiomatisation External Searching for Timed Automata Surender Baswana, Sandeep Sen Huimin Lin and Wang Yi 11:10-11:30 Tea 11:30-12:30 124. Text Sparsification via 120. Semantic Theory for Local Maxima Heterogeneous System Design Pierluigi Cresceznzi, Alberto Rance Cleaveland, Gerald Del Lungo, Roberto Grossi, Luettgen Elena Lodi, Linda Palgi, Gianluca Rossi 38. Approximate Swapped Matching 133. Formal Verification of the A Amir, M Lewenstein, E. Porat Ricart-Agrawala Algorithm Ekaterina Sedletsky, Amir Pnueli, Mordechai Ben-Ari 12:30-14:00 Lunch 14:00-15:00 Invited Talk: Jose Meseguer Rewriting Logic as a Metalogical Framework 15:00-15:30 Tea 15:30-17:00 96. On distribution-specific 117. A General Framework for learning with membership queries Types in Graph Rewriting versus pseudorandom generation Barbara Koenig Johannes K�bler, Wolfang Lindner 69. $\Theta_2^p$-completeness: 146. The Ground Congruence for A classical approach for new Chi Calculus results Yuxi Fu, Zhenrong Yang Joel Vogel, Holger Spakowski 110. Is the Standard Proof System 122. Inheritance in the Join for SAT P-optimal? Calculus Johannes K�bler, Jochen Messner Cedric Fournet, Cosimo Laneve, Luc Maranget Didier Remy 15 December 2000 9:00-10:00 Invited Talk: Martin Gr�tschel Frequency Assignment in Mobile Phone Systems 10:10-11:10 65. Approximation Algorithms 118. The Fine Structure of for Bandwidth and Storage Game Lambda Models Allocation Problems under Real Pietro Di Gianantonio, Time Constraints Gianluca Franco Stefano Leonardi, Alberto Marchetti-Spaccamela, Andrea Vitaletti 37. Dynamic Spectrum Allocation: 127. Strong Normalisation of The Impotency of Duration Second Order Symmetric Notification Lambda-calculus Bala Kalyanasundaram, Kirk Pruhs Michel Parigot 11:10-11:30 Tea 11:30-12:30 94. Scheduling to minimize the 49. Keeping Track of the Latest average completion time of Gossip in Shared Memory Systems dedicated tasks Bharat Adsul, Aranyak Mehta, Foto Afrati, Eviripidis Bampis, Milind Sohoni Aleksei V. Fishin, Klaus Jansen Claire Keyon 73. Hunting for Functionally 123. On Concurrent Knowledge Analogous Genes and Logical Clock Abstractions M. T. Hallett, J. Lagergren Ajay Kshemkalyani 12:30-14:00 Lunch 14:00-15:00 Invited Talk: Peter Buneman Data Provenance: Some Basic Issues 15:00-15:30 Tea 15:30-16:30 20. Decidable Hierarchies of Starfree Languages Christian Glasser, Heinz Schmitz 58. Prefix languages of Church-Rosser Languages Jens R. Woinowski 16:30-17:00 Closing Organization: FST TCS 2000 is being organized by the Indian Institute of Technology, Delhi under the aegis of the Indian Association for Research in Computer Science (IARCS). -- Sanjiva Prasad Associate Professor Department of Computer Science and Engineering sanjiva@cse.iitd.ernet.in Indian Institute of Technology, Delhi (Off) +91 11 659 1294 Hauz Khas, New Delhi 110016 (Res) +91 11 659 1684 INDIA (Fax) +91 11 686 8765 http://www.cse.iitd.ernet.in/~sanjiva