## Foundations of Software Technology and Theoretical Computer Science: 19th Conference, Chennai, India, December 13-15, 1999 Proceedingsth 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 |

450 | |

### Other editions - View all

Foundations of Software Technology and Theoretical Computer Science: 19th ... C. Pandu Rangan,V. Raman,R. Ramanujam No preview available - 1999 |

### Common terms and phrases

algebras algorithm apply asynchronous automata automaton binary bisimulation block Büchi Büchi automata buddy system calculus called cell complexity Computational Geometry Computer Science condition consider constraint construction contains context corresponding deﬁne defined deﬁnition denote deterministic DIAT tree distribution DNA computing edges equivalent exists explicit substitutions facet failure detector finite formula function given graph induction infinite input join-calculus Kolmogorov complexity Kripke Kripke structure labeled language Lemma linear LNCS lower bound lower envelope LTOBDDs modal model checking multiset nondeterministic nondeterministic variables obtained operational semantics operations pair paper path polynomial pomsets problem Proc proof properties Proposition protocol query Rabin automaton recursive redex relation resp result rule semantics sequence Sharir Springer-Verlag Streett Streett automaton structure subset superblock temporal logic Theorem transition system unary nodes vertices Voronoi diagrams weak