Foundations of Software Technology and Theoretical Computer Science

1. Front Matter

   PDF

2. Efficient resolution of singularities of plane curves

   • Dexter Kozen

   Pages 1-11

3. On the interactive complexity of graph reliability

   • Jean-Marc Couveignes, Juan Francisco Diaz-Frias, Michel de Rougemont, Miklos Santha

   Pages 12-23

4. Matching upper and lower bounds for simulations of several tapes on one multidimensional tape

   • Martin Dietzfelbinger, Martin Hühne

   Pages 24-35

5. The complexity of computing over quasigroups

   • Hervé Caussinus, François Lemieux

   Pages 36-47

6. Non-commutative computation, depth reduction, and skew circuits (extended abstract)

   • Meena Mahajan, V Vinay

   Pages 48-59

7. Inductive definitions and type theory an introduction (preliminary version)

   • Thierry Coquand, Peter Dybjer

   Pages 60-76

8. Interpreter verification for a functional language

   • Manfred Broy, Ursula Hinkel, Tobias Nipkow, Christian Prehofer, Birgit Schieder

   Pages 77-88

9. An epistemic foundation for logic programming with uncertainty

   • Laks V. S. Lakshmanan

   Pages 89-100

10. On typed calculi with a merge operator

    • Hideki Tsuiki

    Pages 101-112

11. Incremental algorithms for the single-source shortest path problem

    • Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni

    Pages 113-124

12. An O(n) algorithm for realizing degree sequences

    • Srinivasa Rao Arikati, Anil Maheshwari

    Pages 125-136

13. Coloring semi-random graphs in polynomial expected time

    • C. R. Subramanian, C. E. Veni Madhavan

    Pages 137-148

14. Finite-state strategies in regular infinite games

    • Wolfgang Thomas

    Pages 149-158

15. Location of the largest empty rectangle among arbitrary obstacles

    • Subhas C. Nandy, Arani Sinha, Bhargab B. Bhattacharya

    Pages 159-170

16. Efficient parallel and linear time sequential split decomposition (extended abstract)

    • Elias Dahlhaus

    Pages 171-180

17. Algorithms for convex visibility problems

    • Supriya Biswas, D. Chithra Prasad, Sudebkumar Prasant Pal

    Pages 181-192

18. Lower bounds for parallel algebraic decision trees, complexity of convex hulls and related problems

    • Sandeep Sen

    Pages 193-204

19. Localities and failures (extended summary)

    • Roberto M. Amadio, Sanjiva Prasad

    Pages 205-216

20. Priority and abstraction in process algebra

    • V. Natarajan, I. Christoff, L. Christoff, R. Cleaveland

    Pages 217-230

This volume presents the proceedings of the 14th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FST&TCS-14, held in Madras, India in December 1994.
Besides the five invited papers by well-known researchers, it includes 31 full refereed research papers selected out of a total of 140 submissions. The papers contribute to the whole area of theoretical computer science with an emphasis on algorithms and complexity. Other topics covered are program semantics, program verification, formal logic, computational geometry, concurrency, unification, and discrete mathematics.

• algorithm
• algorithms
• complexity
• computational geometry
• computer
• computer science
• formal logic
• logic
• semantics
• verification
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics