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

by Kapoor, Sanjiv; Prasad, Sanjiva

• ISBN13: 9783540414131
• ISBN10: 3540414134
• Format: Paperback
• Copyright: 2001-03-01
• Publisher: Springer Verlag

Summary

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.

Table of Contents

Invited Presentations
Model Checking: Theory into Practice	1	(10)
E. Allen Emerson
An Algebra for XML Query	11	(35)
Mary Fernandez
Jerome Simeon
Philip Wadler
Irregularities of Distribution, Derandomization, and Complexity Theory	46	(9)
Bernard Chazelle
Rewriting Logic as a Metalogical Framework	55	(26)
David Basin
Manuel Clavel
Jose Meseguer
Frequency Assignment in Mobile Phone Systems	81	(6)
Martin Grotschel
Data Provenance: Some Basic Issues	87	(7)
Peter Buneman
Sanjeev Khanna
Wang-Chiew Tan
Contributions
Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and Its Connections with Principal Partition	94	(12)
Sachin B. Patkar
H. Narayanan
On-Line Edge-Coloring with a Fixed Number of Colors	106	(11)
Lene Monrad Favrholdt
Morten Nyhave Nielsen
On Approximability of the Independent/Connected Edge Dominating Set Problems	117	(10)
Toshihiro Fujito
Model Checking CTL Properties of Pushdown Systems	127	(12)
Igor Walukiewicz
A Decidable Dense Branching-Time Temporal Logic	139	(12)
Salvatore La Torre
Margherita Napoli
Fair Equivalence Relations	151	(13)
Orna Kupferman
Nir Piterman
Moshe Y. Vardi
Arithmetic Circuits and Polynomial Replacement Systems	164	(12)
Pierre McKenzie
Heribert Vollmer
Klaus W. Wagner
Depth-3 Arithmetic Circuits for S2n (X) and Extensions of the Graham-Pollack Theorem	176	(12)
Jaikumar Radhakrishnan
Pranab Sen
Sundar Vishwanathan
The Bounded Weak Monadic Quantifier Alternation Hierarchy of Equational Graphs Is Infinite	188	(13)
Olivier Ly
Combining Semantics with Non-standard Interpreter Hierarchies	201	(13)
Sergei Abramov
Robert Gluck
Using Modes to Ensure Subject Reduction for Typed Logic Programs with Subtyping	214	(13)
Jan-Georg Smaus
Francois Fages
Pierre Deransart
Dynamically Ordered Probabilistic Choice Logic Programming	227	(13)
Marina De Vos
Dirk Vermeir
Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems	240	(12)
Michael R. Fellows
Catherine McCartin
Frances A. Rosamond
Ulrike Stege
Planar Graph Blocking for External Searching	252	(12)
Surender Baswana
Sandeep Sen
A Complete Fragment of Higher-Order Duration μ-Calculus	264	(13)
Dimitar P. Guelev
A Complete Axiomatisation for Timed Automata	277	(13)
Huimin Lin
Wang Yi
Text Sparsification via Local Maxima	290	(12)
Pilu Crescenzi
Alberto Del Lungo
Roberto Grossi
Elena Lodi
Linda Pagli
Gianluca Rossi
Approximate Swapped Matching	302	(10)
Amihood Amir
Moshe Lewenstein
Ely Porat
A Semantic Theory for Heterogeneous System Design	312	(13)
Rance Cleaveland
Gerald Luttgen
Formal Verification of the Ricart-Agrawala Algorithm	325	(11)
Ekaterina Sedletsky
Amir Pnueli
Mordechai Ben-Ari
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation	336	(12)
Johannes Kobler
Wolfgang Linder
Θp2-Completeness: A Classical Approach for New Results	348	(13)
Holger Spakowski
Jorg Vogel
Is the Standard Proof System for SAT P-Optimal?	361	(12)
Johannes Kobler
Jochen Messner
A General Framework for Types in Graph Rewriting	373	(12)
Barbara Konig
The Ground Congruence for Chi Calculus	385	(12)
Yuxi Fu
Zhenrong Yang
Inheritance in the Join Calculus	397	(12)
Cedric Fournet
Cosimo Laneve
Luc Maranget
Didier Remy
Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints	409	(12)
Stefano Leonardi
Alberto Marchetti-Spaccamela
Andrea Vitaletti
Dynamic Spectrum Allocation: The Impotency of Duration Notification	421	(8)
Bala Kalyanasundaram
Kirk Pruhs
The Fine Structure of Game Lambda Models	429	(13)
Pietro Di Gianantonio
Gianluca Franco
Strong Normalization of Second Order Symmetric λ-Calculus	442	(12)
Michel Parigot
Scheduling to Minimize the Average Completion Time of Dedicated Tasks	454	(11)
Foto Afrati
Evripidis Bampis
Aleksei V. Fishkin
Klaus Jansen
Claire Kenyon
Hunting for Functionally Analogous Genes	465	(12)
Michael T. Hallett
Jens Lagergren
Keeping Track of the Latest Gossip in Shared Memory Systems	477	(12)
Bharat Adsul
Aranyak Mehta
Milind Sohoni
Concurrent Knowledge and Logical Clock Abstractions	489	(14)
Ajay D. Kshemkalyani
Decidable Hierarchies of Starfree Languages	503	(13)
Christian Glaser
Heinz Schmitz
Prefix Languages of Church-Rosser Languages	516	(15)
Jens R. Woinowski
Author Index	531