Foundations of Software Technology and Theoretical Computer Science

1. Front Matter

   PDF

2. Planar point location revisited (A guided tour of a decade of research)

   • Franco P. Preparata

   Pages 1-17

3. Computing a viewpoint of a set of points inside a polygon

   • Subir Kumar Ghosh

   Pages 18-29

4. Analysis of preflow push algorithms for maximum network flow

   • J. Cheriyan, S. N. Maheshwari

   Pages 30-48

5. A new linear algorithm for the two path problem on chordal graphs

   • S. V. Krishnan, C. Pandu Rangan, S. Seshadri

   Pages 49-66

6. Extending planar graph algorithms to K _3,3-free graphs

   • Samir Khuller

   Pages 67-79

7. Constant-space string-matching

   • Maxime Crochemore

   Pages 80-87

8. Inherent nonslicibility of rectangular duals in VLSI floorplanning

   • Susmita Sur-Kolay, Bhargab B. Bhattacharya

   Pages 88-107

9. Path planning with local information

   • Amitava Datta, Kamala Krithivasan

   Pages 108-121

10. Linear broadcast routing

    • Ching-Tsun Chou, Inder S. Gopal

    Pages 122-122

11. Predicting deadlock in store-and-forward networks

    • Claudio Arbib, Giuseppe F. Italiano, Alessandro Panconesi

    Pages 123-142

12. On parallel sorting and addition with concurrent writes

    • Sanjeev Saxena, P. C. P. Bhatt, V. C. Prasad

    Pages 143-153

13. An optimal parallel algorithm for sorting presorted files

    • Christos Levcopoulos, Ola Petersson

    Pages 154-160

14. Superlinear speedup in parallel state-space search

    • V. Nageshwara Rao, Vipin Kumar

    Pages 161-174

15. Circuit definitions of nondeterministic complexity classes

    • H. Venkateswaran

    Pages 175-192

16. Non-uniform proof systems: A new framework to describe non-uniform and probabilistic complexity classes

    • Jürgen Kämper

    Pages 193-210

17. Padding, commitment and self-reducibility

    • Sanjeev N. Khadilkar, Somenath Biswas

    Pages 211-224

18. The complexity of a counting finite-state automaton

    • Craig A. Rich, Giora Slutzki

    Pages 225-239

19. A hierarchy theorem for pram-based complexity classes

    • Walter W. Kirchherr

    Pages 240-249

20. A natural deduction treatment of operational semantics

    • Rod Burstall, Furio Honsell

    Pages 250-269

This volume contains the proceedings of the 8th Conference on Foundations of Software Technology and Theoretical Computer Science held in Pune, India, on December 21-23, 1988. This internationally well-established Indian conference series provides a forum for actively investigating the interface between theory and practice of Software Science. It also gives an annual occasion for interaction between active research communities in India and abroad. Besides attractive invited papers the volume contains carefully reviewed submitted papers on the following topics: Automata and Formal Languages, Graph Algorithms and Geometric Algorithms, Distributed Computing, Parallel Algorithms, Database Theory, Logic Programming, Programming Methodology, Theory of Algorithms, Semantics and Complexity.

• Algorithms
• Automat
• Processing
• Resolution
• Variable
• automata
• complexity
• computer
• distributed computing
• formal language
• knowledge base
• programming
• proving
• semantics
• theorem proving
• algorithm analysis and problem complexity

Policies and ethics