Foundations of Software Technology and Theoretical Computer Science

1. Front Matter

   PDF

2. System specification and refinement in temporal logic

   • Amir Pnueli

   Pages 1-38

3. Fixed points of Büchi automata

   • Mads Dam

   Pages 39-50

4. An automata-theoretic decision procedure for Future Interval Logic

   • Y. S. Ramakrishna, L. K. Dillon, L. E. Moser, P. M. Melliar-Smith, G. Kutty

   Pages 51-67

5. Improving the results of static analyses of programs by local decreasing iterations

   • Philippe Granger

   Pages 68-79

6. Implicit point location in arrangements of line segments, with an application to motion planning

   • Pankaj K. Agarwal, Marc van Kreveld

   Pages 80-91

7. An optimal algorithm for the intersection radius of a set of convex polygons

   • Shreesh Jadhav, Asish Mukhopadhyay, Binay Bhattacharya

   Pages 92-103

8. C-sensitive triangulations approximate the minmax length triangulation

   • Christos Levcopoulos, Andrzej Lingas

   Pages 104-115

9. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy

   • Harry Buhrman, Steven Homer

   Pages 116-127

10. Structural average case complexity

    • Rainer Schuler, Tomoyuki Yamakami

    Pages 128-139

11. On bounded truth-table, conjunctive, and randomized reductions to sparse sets

    • V. Arvind, J. Köbler, M. Mundhenk

    Pages 140-151

12. One-way functions and isomorphism conjecture

    • K. Ganesan

    Pages 152-163

13. Solving the Lagrangian dual when the number of constraints is fixed

    • Richa Agarwala, David Fernández-Baca

    Pages 164-175

14. Superfiniteness of query answers in deductive databases: An automata-theoretic approach

    • Laks V. S. Lakshmanan, Daniel A. Nonen

    Pages 176-190

15. Proving polynomials positive

    • Joachim Steinbach

    Pages 191-202

16. An abstract interpretation scheme for groundness, freeness, and sharing analysis of logic programs

    • Renganathan Sundararajan, John S. Conery

    Pages 203-216

17. Polymorphic typing by abstract interpretation

    • B. Monsuez

    Pages 217-228

18. The Gallina specification language: A case study

    • Gérard Huet

    Pages 229-240

19. Verification of large software systems

    • Wolfgang Reif

    Pages 241-252

20. Detection of unstable predicates in distributed programs

    • Vijay K. Garg, Brian Waldecker

    Pages 253-264

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.

• Algorithms
• Computational Geometry
• Computer-Geometrie
• Formal Languages
• Formale Sprachen
• Grammars
• Graph Theory
• Network Operations
• Netzwerk-Operationen
• algorithm
• logic

Policies and ethics