Foundations of Software Technology and Theoretical Computer Science: 19th Conference, Chennai, India, December 13-15, 1999 Proceedings (Lecture Notes in Computer Science, 1738)

This book constitutes the refereed proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'99, held in Chennai, India, in December 1999. The 30 revised full papers presented were carefully reviewed and selected from a total of 84 submissions. Also included are six invited contributions. The papers presented address all current issues in theoretical computer science and programming theory. 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. Invited Talk 1 -- Recent Developments In The Theory Of Arrangements Of Surfaces -- Session 1(a) -- Dynamic Compressed Hyperoctrees With Application To The N-body Problem -- Largest Empty Rectangle Among A Point Set -- Session 1(b) -- Renaming Is Necessary In Timed Regular Expressions -- Product Interval Automata: A Subclass Of Timed Automata -- Session 2(a) -- The Complexity Of Rebalancing A Binary Search Tree -- Fast Allocation And Deallocation With An Improved Buddy System -- Session 2(b) -- Optimal Bounds For Transformations Of ?-automata -- Ctl+ Is Exponentially More Succinct Than Ctl -- Invited Talk 2 -- A Top-down Look At A Secure Message -- Session 3 -- Explaining Updates By Minimal Sums -- A Foundation For Hybrid Knowledge Bases -- Session 4 -- Hoare Logic For Mutual Recursion And Local Variables -- Invited Talk 3 -- Explicit Substitutions And Programming Languages -- Session 5(a) -- Approximation Algorithms For Routing And Call Scheduling In All-optical Chains And Rings --^ A Randomized Algorithm For Flow Shop Scheduling -- Session 5(b) -- Synthesizing Distributed Transition Systems From Global Specifications -- Beyond Region Graphs: Symbolic Forward Analysis Of Timed Automata -- Session 6 -- Implicit Temporal Query Languages: Towards Completeness -- On The Undecidability Of Some Sub-classical First-order Logics -- Invited Talk 4 -- How To Compute With Dna -- Session 7(a) -- A High Girth Graph Construction And A Lower Bound For Hitting Set Size For Combinatorial Rectangles -- Protecting Facets In Layered Manufacturing -- Session 7(b) -- The Receptive Distributed ?-calculus -- Series And Parallel Operations On Pomsets -- Session 8 -- Unreliable Failure Detectors With Limited Scope Accuracy And An Application To Consensus -- Invited Talk 5 -- Graph Isomorphism: Its Complexity And Algorithms -- Session 9(a) -- Computing With Restricted Nondeterminism: The Dependence Of The Obdd Size On The Number Of Nondeterministic Variables --^ Lower Bounds For Linear Transformed Obdds And Fbdds -- Session 9(b) -- A Unifying Framework For Model Checking Labeled Kripke Structures, Modal Transition Systems, And Interval Transition Systems -- Graded Modalities And Resource Bisimulation -- Session 10(a) -- The Non-recursive Power Of Erroneous Computation -- Analysis Of Quantum Functions -- Session 10(b) -- On Sets Growing Continuously -- Model Checking Knowledge And Time In Systems With Perfect Recall -- Fst&tcs — Isaac Joint Session Talks -- The Engineering Of Some Bipartite Matching Programs. C. Pandu Rangan, V. Raman, R. Ramanujam (eds.). Includes Bibliographical References And Index. Recent Developments in the Theory of Arrangements of Surfaces....Pages 1-21 Dynamic Compressed Hyperoctrees with Application to the N-body Problem....Pages 21-33 Largest Empty Rectangle among a Point Set....Pages 34-46 Renaming Is Necessary in Timed Regular Expressions....Pages 47-59 Product Interval Automata: A Subclass of Timed Automata....Pages 60-71 The Complexity of Rebalancing a Binary Search Tree....Pages 72-83 Fast Allocation and Deallocation with an Improved Buddy System....Pages 84-96 Optimal Bounds for Transformations of ω-Automata....Pages 97-109 CTL + Is Exponentially More Succinct than CTL....Pages 110-121 A Top-Down Look at a Secure Message....Pages 122-141 Explaining Updates by Minimal Sums....Pages 142-154 A Foundation for Hybrid Knowledge Bases....Pages 155-167 Hoare Logic for Mutual Recursion and Local Variables....Pages 168-180 Explicit Substitutions and Programming Languages....Pages 181-200 Approximation Algorithms for Routing and Call Scheduling in All-Optical Chains and Rings....Pages 201-213 A Randomized Algorithm for Flow Shop Scheduling....Pages 213-218 Synthesizing Distributed Transition Systems from Global Specifications....Pages 219-231 Beyond Region Graphs: Symbolic Forward Analysis of Timed Automata....Pages 232-244 Implicit Temporal Query Languages: Towards Completeness....Pages 245-257 On the Undecidability of Some Sub-classical First-Order Logics....Pages 258-268 How to Compute with DNA....Pages 269-282 A High Girth Graph Construction and a Lower Bound for Hitting Set Size for Combinatorial Rectangles....Pages 283-290 Protecting Facets in Layered Manufacturing....Pages 291-303 The Receptive Distributed π-Calculus....Pages 304-315 Series and Parallel Operations on Pomsets....Pages 316-328 Unreliable Failure Detectors with Limited Scope Accuracy and an Application to Consensus....Pages 329-341 Graph Isomorphism: Its Complexity and Algorithms....Pages 341-341 Computing with Restricted Nondeterminism: The Dependence of the OBDD Size on the Number of Nondeterministic Variables....Pages 342-355 Lower Bounds for Linear Transformed OBDDs and FBDDs....Pages 356-368 A Unifying Framework for Model Checking Labeled Kripke Structures, Modal Transition Systems, and Interval Transition Systems....Pages 369-380 Graded Modalities and Resource Bisimulation....Pages 381-393 The Non-recursive Power of Erroneous Computation....Pages 394-406 Analysis of Quantum Functions....Pages 407-419 On Sets Growing Continuously....Pages 420-431 Model Checking Knowledge and Time in Systems with Perfect Recall....Pages 432-445 The Engineering of Some Bipartite Matching Programs....Pages 446-449 Foundations of Software Technology and Theoretical Computer Science: 19th Conference Chennai, India, December 13-15, 1999 Proceedings Author: C. Pandu Rangan, V. Raman, R. Ramanujam Published by Springer Berlin Heidelberg ISBN: 978-3-540-66836-7 DOI: 10.1007/3-540-46691-6 Table of Contents: Recent Developments in the Theory of Arrangements of Surfaces Dynamic Compressed Hyperoctrees with Application to the N-body Problem Largest Empty Rectangle among a Point Set Renaming Is Necessary in Timed Regular Expressions Product Interval Automata: A Subclass of Timed Automata The Complexity of Rebalancing a Binary Search Tree Fast Allocation and Deallocation with an Improved Buddy System Optimal Bounds for Transformations of ω-Automata CTL+ Is Exponentially More Succinct than CTL A Top-Down Look at a Secure Message Explaining Updates by Minimal Sums A Foundation for Hybrid Knowledge Bases Hoare Logic for Mutual Recursion and Local Variables Explicit Substitutions and Programming Languages Approximation Algorithms for Routing and Call Scheduling in All-Optical Chains and Rings A Randomized Algorithm for Flow Shop Scheduling Synthesizing Distributed Transition Systems from Global Specifications Beyond Region Graphs: Symbolic Forward Analysis of Timed Automata Implicit Temporal Query Languages: Towards Completeness On the Undecidability of Some Sub-classical First-Order Logics