Foundations of Software Technology and Theoretical Computer Science: 12th Conference New Delhi, India, December 18–20, 1992 Proceedings

System specification and refinement in temporal logic....Pages 1-38
Fixed points of Büchi automata....Pages 39-50
An automata-theoretic decision procedure for Future Interval Logic....Pages 51-67
Improving the results of static analyses of programs by local decreasing iterations....Pages 68-79
Implicit point location in arrangements of line segments, with an application to motion planning....Pages 80-91
An optimal algorithm for the intersection radius of a set of convex polygons....Pages 92-103
C-sensitive triangulations approximate the minmax length triangulation....Pages 104-115
Superpolynomial circuits, almost sparse oracles and the exponential hierarchy....Pages 116-127
Structural average case complexity....Pages 128-139
On bounded truth-table, conjunctive, and randomized reductions to sparse sets....Pages 140-151
One-way functions and isomorphism conjecture....Pages 152-163
Solving the Lagrangian dual when the number of constraints is fixed....Pages 164-175
Superfiniteness of query answers in deductive databases: An automata-theoretic approach....Pages 176-190
Proving polynomials positive....Pages 191-202
An abstract interpretation scheme for groundness, freeness, and sharing analysis of logic programs....Pages 203-216
Polymorphic typing by abstract interpretation....Pages 217-228
The Gallina specification language: A case study....Pages 229-240
Verification of large software systems....Pages 241-252
Detection of unstable predicates in distributed programs....Pages 253-264
Fast sequential and randomised parallel algorithms for rigidity and approximate min k-cut....Pages 265-278
Approximation through local optimality: Designing networks with small degree....Pages 279-290
Games and full Completeness for multiplicative Linear Logic....Pages 291-301
Real-time calculi and expansion theorems....Pages 302-315
Branching bisimulation for context-free processes....Pages 316-327
CCS, locations and asynchronous transition systems....Pages 328-341
Reasoning about safety and liveness properties for probabilistic processes....Pages 342-355
String matching under a general matching relation....Pages 356-367
On the complexity of Certified Write All Algorithms....Pages 368-379
Selection from read-only memory and sorting with optimum data movement....Pages 380-391
Some observations on 2-way probabilistic finite automata....Pages 392-403
Recent developments in algorithms for the maximum-flow problem....Pages 404-404