8. FSTTCS 1988: Pune, India

Kesav V. Nori, Sanjeev Kumar (Eds.): Foundations of Software Technology and Theoretical Computer Science, Eighth Conference, Pune, India, December 21-23, 1988, Proceedings. Lecture Notes in Computer Science 338 Springer 1988, ISBN 3-540-50517-2

Invited Talk

Franco P. Preparata:
Planar Point Location Revisited (A Guided Tour of a Decade of Research). 1-17

Algorithms

Subir Kumar Ghosh:
Computing a Viewpoint of a Set of Points Inside a Polygon. 18-29
Joseph Cheriyan, S. N. Maheshwari:
Analysis of Preflow Push Algorithms for Maximum Network Flow. 30-48
S. V. Krishnan, C. Pandu Rangan, S. Seshadri:
A New Linear Algorithm for the Two Path Problem on Chordal Graphs. 49-66
Samir Khuller:
Extending Planar Graph Algorithms to K 3, 3-free Graphs. 67-79

Algorithms

Maxime Crochemore:
Constant-Space String-Matching. 80-87
Susmita Sur-Kolay, Bhargab B. Bhattacharya:
Inherent Nonslicibility of Rectangular Duals in VLSI Floorplanning. 88-107
Amitava Datta, Kamala Krithivasan:
Path Planning with Local Information. 108-121

Algorithms

Ching-Tsun Chou:
Linear Broadcast Routing. 122
Claudio Arbib, Giuseppe F. Italiano, Alessandro Panconesi:
Predicting deadlock in Store-and-Forward Networks. 123-142
Sanjeev Saxena, P. C. P. Bhatt, V. C. Prasad:
On Parallel Sorting and Addition with Concurrent Writes. 143-153
Christos Levcopoulos:
On Optimal Parallel Algorithm for Sorting Presorted Files. 154-160
V. Nageshwara Rao, Vipin Kumar:
Superlinear Speedup in Parallel State-Space Search. 161-174

Complexity

H. Venkateswaran:
Circuit Definitions of Nondeterministic Complexity Classes. 175-192
Jürgen Kämper:
Non-Uniform Proof System: A New Framework to Describe Non-Uniform and Probabalistic Complexity Classes. 193-210
Sanjeev N. Khadilkar:
Padding, Commitment and Self-reducability. 211-224
Craig A. Rich:
The Complexity of a Counting Finite-State Automaton. 225-239
Walter W. Kirchherr:
A Hierarchy Theorem for Pram-Based Complexity Classes. 240-249

Invited Talk

Rod M. Burstall, Furio Honsell:
A Natural Deduction treatment of Operational Semantics. 250-269

Semantics

Patrick Bellot:
Unformly Applicative Structures, A Theory of Computability and Polyadic Functions. 270-285
Baruch Awerbuch, Lefteris M. Kirousis, Evangelos Kranakis, Paul M. B. Vitányi:
A Proof Technique for Register Automicity. 286-303
Jules Desharnais, Nazim H. Madhavji:
Relation Level Semantics. 304-328
Martin C. Henson, Raymond Turner:
A Constructive Set Theory for Program Development. 329-347
Prakash Panangaden:
McCarthy's Amb Cannot Implement Fair Merge. 348-363

Invited Talk

Koichi Furukawa, Kazunori Ueda:
GHC - A Language for a New Age of Parallel Programming. 364-376

Logic Programming and Theorem Proving

Keshav Pingali, Kattamuri Ekanadham:
Accumulators: A New Logic Variable Abstractions for Functional Languages. 377-399
K. S. H. S. R. Bhatta, Harish Karnick:
A Resolution Rule for Well-Formed Formulae. 400-418
Stéphane Kaplan:
Algebraic and Operational Semantics of Positive/Negative Conditional Algebraic Specification. 419-434
Deepak Kapur, David R. Musser, Paliath Narendran, Jonathan Stillman:
Semi-Unification. 435-454

Databases and Knowledgebases

Alain Beauvieux:
A Method to Check Knowledge Base Consistency. 455-468
José Luiz Fiadeiro, Amílcar Sernadas, Cristina Sernadas:
Knowledgebases as Structured Theories. 469-486
Jürgen M. Janas:
On Functional Independencies. 487-508
Bharat K. Bhargava, Shirley Browne:
A Generic Algorithm for Transaction Processing During Network Partitioning. 509-519