11. FSTTCS 1991: New Delhi, India

Invited Papers

• Manuel Blum:
  Program Checking. 1-9
  
• Andreas Blass, Yuri Gurevich:
  Randomizing Reductions of Search Problems. 10-24
  

Term Rewriting, Type Theory

• David Sands:
  Time Analysis, Cost Equivalence and Program Refinement. 25-39
  
• Subrata Mitra, G. Sivakumar:
  AC-Equation Solving. 40-56
  
• Qing-Ping Tan, Huo-Wang Chen:
  On the Operational Interpretation of Complex Types. 57-70
  

Semantics, Chair: R. K. Shyamasundar

• Kamal Lodaya, Ramaswamy Ramanujam:
  Tense Logics for Local Reasoning in Distributed Systems. 71-88
  
• Luca Aceto, Uffe Engberg:
  Failures Semantics for a Simple Process Language with Refinement. 89-108
  
• Hardi Hungar:
  Correstness of Programs over Poor Signatures. 109-120
  
• John Case, Sanjay Jain, Arun Sharma:
  Complexity Issues for Vacillatory Function Identification. 121-140
  

Automata Theory

• Bertrand Le Saëc, Jean-Eric Pin, Pascal Weil:
  A Purely Algebraic Proof of McNaughton's Theorem on Infinite Words. 141-151
  
• Tao Jiang, Edward McDowell, Bala Ravikumar:
  The Structure and Complexity of Minimal NFA's over a Unary Alphabet. 152-171
  
• Meena Mahajan, Kamala Krithivasan:
  Relativised Cellular Automata and Complexity Classes. 172-185
  
• Sam M. Kim, Robert McNaughton:
  Computing the Order of a Locally Testable Automaton. 186-211
  

Structural Complexity

• Judy Goldsmith, Lane A. Hemachandra, Kenneth Kunen:
  On the Structure and Complexity of Infinite Sets with Minimal Perfect Hash Functions. 212-223
  
• Manindra Agrawal:
  NP-hard Sets and Creativeness over Constant Time Languages. 224-241
  
• Iain A. Stewart:
  Complete Problems Involving Boolean Labelled Structures and Projections Translations. 242-260
  
• V. Vinay:
  Is BP.+P a Probabilistic Class? 261-265
  

Agorithms I

• J. Ian Munro, Venkatesh Raman:
  Fast Sorting In-Place Sorting with O(n) Data. 266-277
  
• Vangelis Th. Paschos:
  A Theorem on the Approximation of Set Cover and Vertex Cover. 278-287
  
• Sachin B. Patkar, H. Narayanan:
  A Fast Algorithm for the Principle Partition of a Graph. 288-306
  

Algorithms II

• Inga Niepel, Peter Rossmanith:
  Uniform Circuits and Exclusive Read PRAMs. 307-318
  
• Martin Fürer:
  Contracting Planar Graphs Efficiency in Parallel. 319-335
  
• Danny Krizanc, Lata Narayanan, Rajeev Raman:
  Fast Deterministic Selection on Mesh-Connected Processor Arrays. 336-346
  

Algorithms III

• Yishay Mansour, James K. Park, Baruch Schieber:
  Improved Selection on Totally Monotone Arrays. 347-359
  
• Christos H. Papadimitriou, P. Venkat Rangan, Martha Sideri:
  Designing Secure Communication Protocols from Trust Specifications. 360-368
  
• Subir Kumar Ghosh, Anil Maheshwari, Sudebkumar Prasant Pal, Sanjeev Saluja, C. E. Veni Madhavan:
  Computing the Shortest Path Tree in a Weak Visibility Polygon. 369-389
  
• Binay K. Bhattacharya:
  Usefulness of Angle-Sweep over Line-Sweep. 390-419
  

Invited Paper

• Glynn Winskel:
  Petri Nets and Transition Systems (Abstract for an invited talk). 420