Foundations of Software Technology and Theoretical Computer Science
18th Conference, Chennai, India, December 17-19, 1998, Proceedings
Published on 25. November 1998
Book
Paperback/Softback
XII, 369 pages
978-3-540-65384-4 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Heidelberg
Germany
Publishing group
Springer Berlin
Target group
College/higher education
Professional and scholarly
Illustrations
biography
Dimensions
Height: 23.5 cm
Width: 15.5 cm
Weight
500 gr
ISBN-13
978-3-540-65384-4 (9783540653844)
DOI
10.1007/b71635
Schweitzer Classification
Content
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.