9. FSTTCS 1989: Bangalore, India

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