Foundations Of Software Technology And Theoretical Computer Science: Ninth Conference, Bangalore, India, December 19-21, 1989. Proceedings (lecture Notes In Computer Science)

"The papers in this volume accepted for the conference on foundations of software technology and theoretical computer science project research results in - Algorithmics: design and analysis of graph, geometric, algebraic and VLSI algorithms; data structures; average analysis; complexity theory; parallel parsing. - Concurrency: algebraic semantics, event structures. - Logic programming: algebraic properties, semantics. - Software technology: program transformations, algebraic methods. These results together with the formal techniques employed to present them reflect current trends pursued by leading research groups around the world. The papers treat their topics in depth by carefully reviewing existing results, developing and demonstrating new techniques and suggesting further directions for research."--Publisher's website A linear-time recognition algorithm for P 4 -reducible graphs....Pages 1-19 Fast parallel approximations of the maximum weighted cut problem through derandomization....Pages 20-29 A new class of separators and planarity of chordal graphs....Pages 30-43 Optimal parallel algorithms on circular-arc graphs....Pages 44-55 Algebraic properties of the space of multivalued and paraconsistent logic programs....Pages 56-67 An autoepistemic logical view of knowledge base....Pages 68-77 A natural semantics for logic programs with negation....Pages 78-88 A transformation system for deductive database modules with perfect model semantics....Pages 89-98 An efficient distributed algorithm for finding articulation points, Bridges, and biconnected components in asynchronous networks....Pages 99-108 Impossibility results in the presence of multiple faulty processes....Pages 109-120 An adaptive regulator approach for the design of load sharing algorithms....Pages 121-130 An algebraic compositional semantics of an object oriented notation with concurrency....Pages 131-142 An axiomatization of event structures....Pages 143-160 Deducing causal relationships in CCS....Pages 161-170 Annotated program transformations....Pages 171-180 Algebraic software development concepts for module and configuration families....Pages 181-192 On the limitations of locally robust positive reductions....Pages 193-203 Query evaluation with null values: How complex is completeness?....Pages 204-222 Average case complexity analysis of RETE pattern-match algorithm and average size of join in Databases....Pages 223-241 The frobenius problem....Pages 242-251 An efficient implicit data structure for path testing and searching in rooted trees and forests....Pages 252-266 Robust decompositions of polyhedra....Pages 267-279 Gate matrix layout revisited: Algorithmic performance and probabilistic analysis....Pages 280-290 Parallel parsing on a one-way linear array of finite-state machines....Pages 291-300 Energy-time trade-offs in VLSI computations....Pages 301-311 Time and real-time in programs....Pages 312-324 A proof system for communicating processes with value-passing (extended abstract)....Pages 325-339