For more than a decade, Foundations of Software Technology and Theoretical Computer Science Conferences have been providing an annual academic computerscience forum for the presentation of new results in the topics of current research in India and abroad. This year, there was a total of 125 papers from 14 countries. Each paper was reviewed by at least three reviewers; based on these reviews, the programme committee selected 28 papers at a meeting held in July 1992 at the Tata Institute of Fundamental Research, Bombay. The selected papers are included in this volume, together with three invited papers: "Games and full completeness for multiplicative linear logic" by S. Abramsky, "Recent developments inalgorithms for the maximum-flow problem" by K. Melhorn, and "System specification and refinement in temporal logic" by A. Pnueli.
Author(s): Amir Pnueli (auth.), Rudrapatna Shyamasundar (eds.)
Series: Lecture Notes in Computer Science 652
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1992
Language: English
Pages: 409
Tags: Logics and Meanings of Programs; Computation by Abstract Devices; Programming Languages, Compilers, Interpreters; Mathematical Logic and Formal Languages; Combinatorics; Computer Graphics
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
