15. FSTTCS 1995: Bangalore, India

Invited Talk

• Mike Paterson, Shlomit Tassa, Uri Zwick: Looking for MUM and DAD: Text-Text Comparisons Do Help. 1-10

Algorithms

• Sanjay Jain: Branch and Bound on the Network Model. 11-21
• Pallab Dasgupta, P. P. Chakrabarti, S. C. De Sarkar: A Near Optimal Algorithm for the Extended Cow-Path Problem in the Presence of Relative Errors. 22-36
• Abhik Roychoudhury, Susmita Sur-Kolay: Efficient Algorithms for Vertex Arboricity of Planar Graphs. 37-51
• Ajit A. Diwan, N. Usharani: A Condition for the Three Colourability of Planar Locally Path Graphs. 52-61

Software Technology

• Peter Baumann, Karl Lermer: A Framework for the Specification of Reactive and Concurrent Systems in Z. 62-79
• Job Zwiers, Ulrich Hannemann, Yassine Lakhnech, Willem P. de Roever: Synthesizing Different Development Paradigms: Combining Top-Down with Bottom-Up Reasoning About Distributed Systems. 80-95
• Jozef Hooman: Verifying Part of the ACCESS.bus Protocol Using PVS. 96-110
• Luigi Petrone: Reusing Batch Parsers as Incremental Parsers. 111-123

Invited Talk

• Prakash Panangaden: The Expressive Power of Indeterminate Primitives in Asynchronous Computation. 124-150

Functionl Programming Theory

• Jacques Garrigue: The Transformation Calculus. 151-165
• Jerzy Tiuryn: Equational Axiomatization of Bicoercibility for Polymorphic Types. 166-179

Distributed Algrithms

• Michel Raynal, André Schiper: From Causal Consistency to Sequential Consistency in Shared Memory Systems. 180-194
• Alexander I. Tomlinson, Vijay K. Garg: Observation of Software for Distributed Systems with RCL. 195-209

Term Rewriting & CLP

• Nick D. Dendris, Lefteris M. Kirousis, Yannis C. Stamatiou, Dimitrios M. Thilikos: Partiality and Approximation Schemes for Local Consistency in Networks of Constraints. 210-224
• Deepak Kapur, G. Sivakumar: Maximal Extensions os Simplification Orderings. 225-239

Complexity Theory

• Rainer Schuler: Average Polynominal Time Is Hard for Exponential Time Under sn-Reductions. 240-247
• Ravi Kumar, D. Sivakumar: On Self-Testing without the Generator Bottleneck. 248-262

Invited Talk

• Mogens Nielsen, Allan Cheng: Obseving Behaviour Categorically. 263-278

Process Algebras

• Paul Caspi, Jean-Claude Fernandez, Alain Girault: An Algorithm for Reducing Binary Branchings. 279-293
• Michele Boreale, Luca Trevisan: On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract). 294-308
• Ashvin Dsouza, Bard Bloom: On the Expressive Power of CCS. 309-323
• Martin Odersky: Polarized Name Passing. 324-337

Algorithms

• R. Balasubramanian, Venkatesh Raman: Path Balance Heuristic for Self-Adjusting Binary Search Trees. 338-348
• S. Rao Kosaraju: Pattern Matching in Compressed Texts. 349-362
• Srinivasa Rao Arikati, Shiva Chaudhuri, Christos D. Zaroliagis: All-Pairs Min-Cut in Sparse Networks. 363-376
• Sandip K. Biswas, Sampath Kannan: Minimizing Space Usage in Evaluation of Expression Trees. 377-390

Invited Talk

• Herbert Edelsbrunner: Smooth Surfaces for Multi-Scale Shape Representation. 391-412

Computational Geometry

• Christos Levcopoulos, Andrzej Lingas, Cao Wang: On Parallel Complexity of Planar Triangulations. 413-427
• Frank Follert, Elmar Schömer, Jürgen Sellen, Michiel H. M. Smid, Christian Thiel: Computing a Largest Empty Anchored Cylinder, and Related Problems. 428-442
• Drago Krznaric, Christos Levcopoulos: Computing Hierarchies of Clusters from the Euclidean Minimum Spanning Tree in Linear Time. 443-455

Temporal Logics and Verification Theory

• Nils Klarlund, Madhavan Mukund, Milind A. Sohoni: Determinizing Büchi Asnchronous Automata. 456-470
• Eugene Asarin, Oded Maler: Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy. 471-483
• Anca Browne, Zohar Manna, Henny Sipma: Generalized Temporal Verification Diagrams. 484-498
• Andrea Bianco, Luca de Alfaro: Model Checking of Probabalistic and Nondeterministic Systems. 499-513