FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science: 21st Conference, Bangalore, India, December 13-15, 2001, Proceedings, Volume 21 (Google eBook)

Ramesh Hariharan, Madhavan Mukund, V. Vinay

Springer, Dec 18, 2001 - Computers - 346 pages

This book constitutes the refereed proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2001, held in Bangalore, India in December 2001. The 23 revised full papers presented together with five invited papers were carefully reviewed and selected from 73 submissions. Among the issues addressed are randomization and derandomization, approximation, Kolmogorov complexity, pseudo-randomness, tree search, model checking, data structures, deterministic algorithms, formal verification, parallel algorithms, minimum-degree spanning trees, scheduling, Petri nets, equivalence logic, and rewriting.

Contents

• Derandomization Lower Bounds and Kolmogorov Complexity: 1
• A Survey: 16
• On Clustering Using Random Walks: 18
• An Introduction to Decidability of DPDA Equivalence: 42
• Semidefinite ProgrammingBased Approximation Algorithms: 57
• Hard Sets and Pseudorandom Generators for Constant Depth Circuits: 58
• The FirstOrder Isomorphism Theorem: 70
• Thresholds and Optimal Binary Comparison Search Trees Extended Abstract: 83
• Distributed LTL Model Checking Based on Negative Cycle Detection: 96
• Computability and Complexity Results for a Spatial Assertion Language for Data Structures: 108
• Using Nondeterminism to Design Efficient Deterministic Algorithms: 120
• Liveness Verification of ReversalBounded Multicounter Machines with a Free Counter Extended Abstract: 132
• A Mechanically Verified Compiling Specification for a Lisp Compiler: 144
• Beyond Regular Model Checking Extended Abstract: 156
• Relations Between Communication Complexity Linear Arrangements and Computational Complexity: 171
• Optimal OutputSensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel: 183
• Bounds and Code Constructions: 195
• Verification of a Leader Election Algorithm in Timed Asynchronous Systems: 207
• Efficient Addition on Field Programmable Gate Arrays: 219
• The Directed MinimumDegree Spanning Tree Problem: 232
• IOEfficient Batched Range Counting and Its Applications to Proximity Problems: 244
• Beyond Message Sequence Graphs: 256
• Grouping Techniques for One Machine Scheduling Subject to Precedence Constraints: 268
• Properties of Distributed TimedArc Petri Nets: 280
• From Falsification to Verification: 292
• On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems: 305
• Range Allocation for Equivalence Logic: 317
• Rewrite Closure for Ground and Cancellative AC Theories: 334
• Author Index: 347

Bibliographic information

• Title: FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science: 21st Conference, Bangalore, India, December 13-15, 2001, Proceedings, Volume 21; FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE; Volume 2245 of Lecture Notes in Computer Science
• Editors: Ramesh Hariharan, Madhavan Mukund, V. Vinay
• Contributors: Ramesh Hariharan, V. Vinay
• Edition: illustrated
• Publisher: Springer, 2001
• ISBN: 3540430024, 9783540430025
• Length: 346 pages
• Subjects: Computers / Computer Science; Computers / Data Processing; Computers / Machine Theory; Computers / Programming / Algorithms; Computers / Programming / General; Computers / Programming Languages / General; Computers / Software Development & Engineering / General; Mathematics / Logic