Foundations of Software Technology and Theoretical Computer Science: 18th Conference, Chennai, India, December 17-19, 1998. Proceedings (Foundations of ... Technology and Theoretical Computer Science)

This book constitutes the refereed proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'98, held in Chennai, India, in December 1998. The 28 revised full papers presented were carefully selected from a total of 93 submissions; also included are six invited contributions. The papers deal with theoretical topics ranging from discrete mathematics and algorithmic aspects to software engineering, program semantics and mathematical logic. Th This Volume Contains The Proceedings Of The 18 Fst&tcs Conference (fo- Dations Of Software Technology And Theoretical Computer Science), Organized Under The Auspices Of The Indian Association For Research In Computing Science (http://www. Imsc. Ernet. In/ Iarcs). This Year’s Conference Attracted 93 Submissions From As Many As 22 Co- Tries. Each Submission Was Reviewed By At Least Three Independent Referees. The Programme Committee Met On August 1 And 2, 1998, At Chennai And Selected 28 Papers For Inclusion In The Conference Programme. We Thank The Programme Committee Members And The Reviewers For Their Sincere E?orts. We Are Fortunate To Have Six Invited Speakers This Year, Providing For A Very Attractive Programme: Rajeev Alur, Ken Mcmillan, Neil Immerman, John Reif, Erik Meineche Schmidt And Umesh Vazirani. The Conference Has Two Theme Sessions: Model Checking (with Invited Talks By Alur And Mcmillan, And 4 C- Tributedpapers),andquantumcomputation(withinvitedtalksbyschmidtand Vazirani). Moreover,the Conference Is Preceded By A Two-day Workshop(dec- Ber 14–15, 1998) On Molecular Computing (organized By Kamala Krithivasan), And A Two-day School (december 15–16, 1998) On Finite Model Theory (or- Nized By Anuj Dawar And Anil Seth). The Molecular Computation Workshop Includes Talks By Natasha Jonoska, Kamala Krithivasan, Georghe Paun, John Reif,yasubumisakakibara,ranisiromoneyandk. G. Subramanian. Thespe- Ers At The Finite Model Theory School Include Anuj Dawar, Martin Grohe, Neil Immerman, Anil Seth, Wolfgang Thomas, Moshe Vardi And Victor Vianu. Invited Talk 1 -- Descriptive Complexity And Model Checking -- Session 1(a) -- Approximation Algorithms With Bounded Performance Guarantees For The Clustered Traveling Salesman Problem -- A Hamiltonian Approach To The Assignment Of Non-reusable Frequencies -- Session 1(b) -- Deadlock Sensitive Types For Lambda Calculus With Resources -- On Encoding P? In M? -- Session 2(a) -- Improved Methods For Approximating Node Weighted Steiner Trees And Connected Dominating Sets -- Red-black Prefetching: An Approximation Algorithm For Parallel Disk Scheduling -- Session 2(b) -- A Synchronous Semantics Of Higher-order Processes For Modeling Reconfigurable Reactive Systems -- Testing Theories For Asynchronous Languages -- Invited Talk 2 -- Alternative Computational Models: A Comparison Of Biomolecular And Quantum Computation -- Session 3 -- Optimal Regular Tree Pattern Matching Using Pushdown Automata -- Locating Matches Of Tree Patterns In Forests -- Session 4 --^ Benefits Of Tree Transducers For Optimizing Functional Programs -- Implementable Failure Detectors In Asynchronous Systems -- Invited Talk 3 -- Brics And Quantum Information Processing -- Session 5(a) -- Martingales And Locality In Distributed Computing -- Space Efficient Suffix Trees -- Session 5(b) -- Formal Verification Of An O.s. Submodule -- Infinite Probabilistic And Nonprobabilistic Testing -- Session 6(a) -- On Generating Strong Elimination Orderings Of Strongly Chordal Graphs -- A Parallel Approximation Algorithm For Minimum Weight Triangulation -- Session 6(b) -- The Power Of Reachability Testing For Timed Automata -- Recursive Mean-value Calculus -- Invited Talk 4 -- Efficient Formal Verification Of Hierarchical Descriptions -- Invited Talk 5 -- Proof Rules For Model Checking Systems With Data -- Session 7 -- Partial Order Reductions For Bisimulation Checking -- First-order-ctl Model Checking -- Session 8(a) --^ On The Complexity Of Counting The Number Of Vertices Moved By Graph Automorphisms -- Remarks On Graph Complexity -- Session 8(b) -- On The Confluence Of Trace Rewriting Systems -- A String-rewriting Characterization Of Muller And Schupp’s Context-free Graphs -- Session 9 -- Different Types Of Monotonicity For Restarting Automata -- A Kleene Iteration For Parallelism -- Invited Talk 6 -- Quantum Computation And Information. V. Arvind, R. Ramanujam (eds.). Proceedings Of The Eighteenth Annual Conference On Foundations Of Software Technology And Theoretical Computer Science. Includes Bibliographical References And Index. Front Matter....Pages - Descriptive Complexity and Model Checking....Pages 1-4 Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem....Pages 6-17 A Hamiltonian Approach to the Assignment of Non-reusable Frequencies....Pages 18-29 Deadlock Sensitive Types for Lambda Calculus with Resources....Pages 30-41 On encoding pπ in mπ ....Pages 42-53 Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets....Pages 54-65 Red-Black Prefetching: An Approximation Algorithm for Parallel Disk Scheduling....Pages 66-77 A Synchronous Semantics of Higher-Order Processes for Modeling Reconfigurable Reactive Systems....Pages 78-89 Testing Theories for Asynchronous Languages....Pages 90-101 Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation....Pages 102-121 Optimal Regular Tree Pattern Matching Using Pushdown Automata....Pages 122-133 Locating Matches of Tree Patterns in Forests....Pages 134-145 Benefits of Tree Transducers for Optimizing Functional Programs....Pages 146-157 Implementable Failure Detectors in Asynchronous Systems....Pages 158-169 BRICS and Quantum Information Processing....Pages 170-173 Martingales and Locality in Distributed Computing....Pages 174-185 Space Efficient Suffix Trees....Pages 186-196 Formal Verification of an O.S. Submodule....Pages 197-208 Infinite Probabilistic and Nonprobabilistic Testing....Pages 209-220 On Generating Strong Elimination Orderings of Strongly Chordal Graphs....Pages 221-232 A Parallel Approximation Algorithm for Minimum Weight Triangulation....Pages 233-244 The Power of Reachability Testing for Timed Automata....Pages 245-256 Recursive Mean-Value Calculus....Pages 257-268 Efficient Formal Verification of Hierarchical Descriptions....Pages 269-269 Proof Rules for Model Checking Systems with Data....Pages 270-270 Partial Order Reductions for Bisimulation Checking....Pages 271-282 First-Order-CTL Model Checking....Pages 283-294 On the Complexity of Counting the Number of Vertices Moved by Graph Automorphisms....Pages 295-306 Remarks on Graph Complexity....Pages 307-318 On the Confluence of Trace Rewriting Systems....Pages 319-330 A String-Rewriting Characterization of Muller and Schupp’s Context-Free Graphs....Pages 331-342 Different Types of Monotonicity for Restarting Automata....Pages 343-354 A Kleene Iteration for Parallelism....Pages 355-366 Quantum Computation and Information....Pages 367-367 Back Matter....Pages - 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