Fst Tcs 2001: Foundations of Software Technology and Theoretical Computer Science : 21st Conference Bangalore, India, December 13-15, 2001 Proceedings

by Hariharan, R.; Kapoor, Sanjiv; Mukund, M.; Vinay, V.

• ISBN13: 9783540430025
• ISBN10: 3540430024
• Format: Paperback
• Copyright: 2001-12-01
• Publisher: Springer Verlag

Summary

Space, light and material: from the meditative ambiance of a chapel or synagogue to the colourful, organic forms of fashion boutiques, the design of an interior space - composed of lighting, the surfaces, textures and colours of materials, finishing and features - creates atmosphere and lends specific character. The growing willingness on the part of designers in recent years to experiment with colours, materials and spatial concepts is demonstrated in the range and diversity of international examples presented in this, the third volume in the series 'In Detail'. All plans and drawings of interiors and furnishings have been carefully researched and drawn by the staff of DETAIL. Three introductory essays by expert authors are followed by 28 exemplary case-studies by such names as Alvaro Siza, Future Systems, Dominique Perrault, and Herzog & de Meuron.

Table of Contents

When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity	p. 1
Approximation Schemes for Geometric NP-Hard Problems: A Survey	p. 16
On Clustering Using Random Walks	p. 18
An Introduction to Decidability of DPDA Equivalence	p. 42
Semidefinite Programming Based Approximation Algorithms	p. 57
Hard Sets and Pseudo-random Generators for Constant Depth Circuits	p. 58
The First-Order Isomorphism Theorem	p. 70
Thresholds and Optimal Binary Comparison Search Trees	p. 83
Distributed LTL Model Checking Based on Negative Cycle Detection	p. 96
Computability and Complexity Results for a Spatial Assertion Language for Data Structures	p. 108
Using Nondeterminism to Design Efficient Deterministic Algorithms	p. 120
Liveness Verification of Reversal-Bounded Multicounter Machines with a Free Counter	p. 132
A Mechanically Verified Compiling Specification for a Lisp Compiler	p. 144
Beyond Regular Model Checking	p. 156
Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity	p. 171
Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel	p. 183
List Decoding from Erasures: Bounds and Code Constructions	p. 195
Verification of a Leader Election Algorithm in Timed Asynchronous Systems	p. 207
Efficient Addition on Field Programmable Gate Arrays	p. 219
The Directed Minimum-Degree Spanning Tree Problem	p. 232
I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems	p. 244
Beyond Message Sequence Graphs	p. 256
Grouping Techniquess for One Machine Scheduling Subject to Precedence Constraints	p. 268
Properties of Distributed Timed-Arc Petri Nets	p. 280
From Falsification to Verification	p. 292
On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems	p. 305
Range Allocation for Equivalence Logic	p. 317
Rewrite Closure for Ground and Cancellative AC Theories	p. 334
Author Index	p. 347
Table of Contents provided by Blackwell. All Rights Reserved.