20. FSTTCS 2000: New Delhi, India

Sanjiv Kapoor, Sanjiva Prasad (Eds.): Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS 2000 New Delhi, India, December 13-15, 2000, Proceedings. Lecture Notes in Computer Science 1974 Springer 2000, ISBN 3-540-41413-4 BibTeX

@proceedings{DBLP:conf/fsttcs/2000,
  editor    = {Sanjiv Kapoor and
               Sanjiva Prasad},
  title     = {Foundations of Software Technology and Theoretical Computer Science,
               20th Conference, FST TCS 2000 New Delhi, India, December 13-15,
               2000, Proceedings},
  booktitle = {FSTTCS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1974},
  year      = {2000},
  isbn      = {3-540-41413-4},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Presentations

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

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