Foundations of Software Technology and Theoretical Computer Science

1. Front Matter

   PDF

2. Looking for MUM and DAD: Text-text comparisons do help

   • Mike Paterson, Shlomit Tassa, Uri Zwick

   Pages 1-10

3. Branch and bound on the network model

   • Sanjay Jain

   Pages 11-21

4. A near optimal algorithm for the extended cow-path problem in the presence of relative errors

   • Pallab Dasgupta, P. P. Chakrabarti, S. C. DeSarkar

   Pages 22-36

5. Efficient algorithms for vertex arboricity of planar graphs

   • Abhik Roychoudhury, Susmita Sur-Kolay

   Pages 37-51

6. A condition for the three colourability of planar locally path graphs

   • Ajit A. Diwan, N. Usharani

   Pages 52-61

7. A framework for the specification of reactive and concurrent systems in Z

   • Peter Baumann, Karl Lermer

   Pages 62-79

8. Synthesizing different development paradigms: Combining top-down with bottom-up reasoning about distributed systems

   • J. Zwiers, U. Hannemann, Y. Lakhneche, W. -P. de Roever

   Pages 80-95

9. Verifying part of the ACCESS.bus protocol using PVS

   • Jozef Hooman

   Pages 96-110

10. Reusing batch parsers as incremental parsers

    • Luigi Petrone

    Pages 111-123

11. The expressive power of indeterminate primitives in asynchronous computation

    • Prakash Panangaden

    Pages 124-150

12. The transformation calculus

    • Jacques Garrigue

    Pages 151-165

13. Equational axiomatization of bicoercibility for polymorphic types

    • Jerzy Tiuryn

    Pages 166-179

14. From causal consistency to sequential consistency in shared memory systems

    • Michel Raynal, André Schiper

    Pages 180-194

15. Observation of software for distributed systems with RCL

    • Alexander I. Tomlinson, Vijay K. Garg

    Pages 195-209

16. Partiality and approximation schemes for local consistency in networks of constraints

    • Nick D. Dendris, Lefteris M. Kirousis, Yannis C. Stamatiou, Dimitris M. Thilikos

    Pages 210-224

17. Maximal extensions of simplification orderings

    • Deepak Kapur, G. Sivakumar

    Pages 225-239

18. Average polynomial time is hard for exponential time under sn-reductions

    • Rainer Schuler

    Pages 240-247

19. On self-testing without the generator bottleneck

    • S. Ravikumar, D. Sivakumar

    Pages 248-262

20. Observing behaviour categorically

    • Mogens Nielsen, Allan Cheng

    Pages 263-278

This book constitutes the refereed proceedings of the 15th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS '95, held in Bangalore, India in December 1995.
The volume presents 31 full revised research papers selected from a total of 106 submissions together with full papers of four invited talks. Among the topics covered are algorithms, software technology, functional programming theory, distributed algorithms, term rewriting and constraint logic programming, complexity theory, process algebras, computational geometry, and temporal logics and verification theory.

• algorithm
• algorithms
• complexity
• complexity theory
• computational geometry
• computer
• computer science
• logic
• programming
• term rewriting
• verification
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics