E-Books durchsuchen

FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science [2001]

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