Foundations of Software Technology and Theoretical Computer Science

A linear-time recognition algorithm for P 4-reducible graphs.- Fast parallel approximations of the maximum weighted cut problem through derandomization.- A new class of separators and planarity of chordal graphs.- Optimal parallel algorithms on circular-arc graphs.- Algebraic properties of the space of multivalued and paraconsistent logic programs.- An autoepistemic logical view of knowledge base.- A natural semantics for logic programs with negation.- A transformation system for deductive database modules with perfect model semantics.- An efficient distributed algorithm for finding articulation points, Bridges, and biconnected components in asynchronous networks.- Impossibility results in the presence of multiple faulty processes.- An adaptive regulator approach for the design of load sharing algorithms.- An algebraic compositional semantics of an object oriented notation with concurrency.- An axiomatization of event structures.- Deducing causal relationships in CCS.- Annotated program transformations.- Algebraic software development concepts for module and configuration families.- On the limitations of locally robust positive reductions.- Query evaluation with null values: How complex is completeness?.- Average case complexity analysis of RETE pattern-match algorithm and average size of join in Databases.- The frobenius problem.- An efficient implicit data structure for path testing and searching in rooted trees and forests.- Robust decompositions of polyhedra.- Gate matrix layout revisited: Algorithmic performance and probabilistic analysis.- Parallel parsing on a one-way linear array of finite-state machines.- Energy-time trade-offs in VLSI computations.- Time and real-time in programs.- A proof system for communicating processes with value-passing (extended abstract).