9. FSTTCS 1989: Bangalore, India

C. E. Veni Madhavan (Ed.): Foundations of Software Technology and Theoretical Computer Science, Ninth Conference, Bangalore, India, December 19-21, 1989, Proceedings. Lecture Notes in Computer Science 405 Springer 1989, ISBN 3-540-52048-1

Graph Algorithms, Chair: G. P. Bhattacharjee

Beverly Jamison, Stephan Olariu:
A Linear-Time Recognition Algorithm for P₄-Reducible Graphs. 1-19
Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis:
Fast Parallel Approximations of hte Maximum Weighted Cut Problem through Derandomization. 20-29
P. Sreenivasa Kumar, C. E. Veni Madhavan:
A New Class of Separators and Planarity of Chordal Graphs. 30-43
A. Srinivasa Rao, C. Pandu Rangan:
Optimal Parallel Algorithms on Circular-Arc Graphs. 44-55

Logic Programming, Chair: G. Venkatesh

V. S. Subrahmanian:
Algebraic Properties of The Space of Multivalued and Paraconsistent Logic Programs. 56-67
Y. J. Jiang:
An Autoepistemic Logical View of Knowledge Base. 68-77
Phan Minh Dung, Kanchana Kanchanasut:
A Natural Semantics for Logic Programs with Negation. 78-88
Michael J. Maher:
A Transformation System for Deductive Database Modules with Perfect Model Semantics. 89-98

Distributed Computing, Chair: L. M. Patnaik

Mohan Ahuja, Yahui Zhu:
An Efficient Distributed Algorithm for Finding Articulation Points, Bridges, and Biconnected Components in Asynchronous Networks. 99-108
Gadi Taubenfeld, Shmuel Katz, Shlomo Moran:
Impossibility Results in the Presence of Multiple Faulty Processes (Preliminary Version). 109-120
Flavio Bonomi, Peter J. Fleming, P. Steinberg:
An Adaptive Regulator Approach for the Design of Load Sharing Algorithms. 121-130

Concurrency, Chair: C. R. Muthukrishnan

Ruth Breu, Elena Zucca:
An Algebraic Compositional Semantics of an Object Oriented Notation with Concurrency. 131-142
Madhavan Mukund, P. S. Thiagarajan:
An Axiomatization of Event Structures. 143-160
Jeremy Gunawardena:
Deducing Causal Relationships in CCS. 161-170

Software Technology, Chair: H. V. Sahasrabuddhe

Victor N. Kasyanov:
Annotated Program Transformations. 171-180
Hartmut Ehrig, Werner Fey, Horst Hansen, Michael Löwe, Dean Jacobs:
Algebraic Software Development Concepts for Module and Configuration Families. 181-192

Complexity and Analysis of Algorithms, Chair: S. Biswas

Lane A. Hemachandra, Sanjay Jain:
On the Limitations of Locally Robust Positive Reductions. 193-203
V. S. Lakshmanan:
Query Evaluation with Null Values: How Complex is Completeness? 204-222
Luc Albert:
Average Case Complexity Analysis of RETE Pattern-Match Algorithm and Average Size of Join in Database. 223-241
Ravi Kannan:
The Frobenius Problem. 242-251

Geometric Algorithms, Chair: C. E. Veni Madhavan

Giorgio Gambosi, Marco Protasi, Maurizio Talamo:
An Efficient Implicit Data Structure for Path Testing and Searching in Rooted Trees and Forests. 252-266
Chandrajit L. Bajaj, Tamal K. Dey:
Robust Decompositions of Polyhedra. 267-279
Sajal K. Das, Narsingh Deo, Sushil K. Prasad:
Gate Matrix Layout Revisited: Algorithmic Performance and Probabilistic Analysis. 280-290

VLSI, Chair: Anshul Kumar

Oscar H. Ibarra, Tao Jiang, Hui Wang:
Parallel Parsing on a One-way Linear Array of Finite-State Machines. 291-300
Akhilesh Tyagi:
Energy-Time Trade-offs in VLSI Computation. 301-311

Invited Papers

Mathai Joseph:
Time and Real-time in Programs. 312-324
Matthew Hennessy:
A Proof System for Communicating Processes with Value-passing (Extended Abstract). 325-339