Foundations of Software Technology and Theoretical Computer Science: 19th Conference, Chennai, India, December 13-15, 1999 Proceedings

Front Cover
th This volume contains the proceedings of the 19 FST&TCS conference (Foundations of Software Technology and Theoretical Computer Science), - ganized under the auspices of the Indian Association for Research in Computing Science (http: //www. imsc. ernet. in/ iarcs). This year's conference attracted 84 submissions from as many as 25 dieren t countries. Each submission was reviewed by at least three independent referees. th After a week-long e-mail discussion, the program committee met on the 7 th and 8 of August, 1999, in Chennai and selected 30 papers for inclusion in the conference program. We thank the program committee members and the reviewers for their sincere eorts. We are fortunate to have ve invited speakers this year, providing for a very attractive program: Mart n Abadi (Bell Labs - Lucent Technologies, Palo Alto, USA), Lila Kari (Univ. Western Ontario, Canada), Jean-Jacques L evy (INRIA, Paris, France), Micha Sharir, (Univ. TelAviv, Israel), andSeinosuke Toda (IEC, Tokyo, Japan). Moreover, theconferenceisprecededbyatwo-dayworkshop(- cember 11{12, 1999) on Data Structures and succeeded by a two-day workshop (December 16-17, 1999) on Foundations of Mobile Computation. The conference also features two joint sessions with the International Symposium on - tomata, Algorithms and Computation (December 16{18, 1999, Chennai): Monika Henzinger (Compaq Systems Research, Palo Alto, USA) is presenting a tutorial on Web algorithmics as the last event of FST&TCS and Kurt Mehlhorn (Max-Planck-Institut, Saarbru ]cken, Germany) is giving a talk on algorithm - gineering as the rst event of ISAAC.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Recent Developments in the Theory of Arrangements of Surfaces
1
Largest Empty Rectangle among a Point Set
34
Renaming Is Necessary in Timed Regular Expressions
47
A Subclass of Timed Automata
60
The Complexity of Rebalancing a Binary Search Tree
72
Fast Allocation and Deallocation with an Improved Buddy System
84
Optimal Bounds for Transformations of ωAutomata
97
CTL+ Is Exponentially More Succinct than CTL
110
On the Undecidability of Some Subclassical FirstOrder Logics
258
How to Compute with DNA
269
A High Girth Graph Construction and a Lower Bound for Hitting Set Size for Combinatorial Rectangles
283
Protecting Facets in Layered Manufacturing
291
The Receptive Distributed πCalculus
304
Series and Parallel Operations on Pomsets
316
Unreliable Failure Detectors with Limited Scope Accuracy and an Application to Consensus
329
The Dependence of the OBDD Size on the Number of Nondeterministic Variables
342

A TopDown Look at a Secure Message
122
Explaining Updates by Minimal Sums
142
A Foundation for Hybrid Knowledge Bases
155
Hoare Logic for Mutual Recursion and Local Variables
168
Explicit Substitutions and Programming Languages
181
Approximation Algorithms for Routing and Call Scheduling in AllOptical Chains and Rings
201
A Randomized Algorithm for Flow Shop Scheduling
213
Synthesizing Distributed Transition Systems from Global Specifications
219
Symbolic Forward Analysis of Timed Automata
232
Towards Completeness
245
Lower Bounds for Linear Transformed OBDDs and FBDDs
356
A Unifying Framework for Model Checking Labeled Kripke Structures Modal Transition Systems and Interval Transition Systems
369
Graded Modalities and Resource Bisimulation
381
The Nonrecursive Power of Erroneous Computation
394
Analysis of Quantum Functions
407
On Sets Growing Continuously
420
Model Checking Knowledge and Time in Systems with Perfect Recall
432
Author Index
450
Copyright

Other editions - View all

Common terms and phrases