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.
Author(s): Micha Sharir (auth.), C. Pandu Rangan, V. Raman, R. Ramanujam (eds.)
Series: Lecture Notes in Computer Science 1738
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1999
Language: English
Pages: 460
Tags: Theory of Computation; Software Engineering/Programming and Operating Systems; Discrete Mathematics in Computer Science
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
