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.
Author(s): Neil Immerman (auth.), Vikraman Arvind, Sundar Ramanujam (eds.)
Series: Lecture Notes in Computer Science 1530
Edition: 1
Publisher: Springer Berlin Heidelberg
Year: 1998
Language: English
Pages: 404
Tags: Theory of Computation; Software Engineering; Programming Languages, Compilers, Interpreters; Discrete Mathematics in Computer Science
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 -
