Foundations of Software Technology and Theoretical Computer Science

Reasoning about linear constraints using parametric queries.- Discriminant circumscription.- Complexity of algebraic specifications.- A new method for undecidability proofs of first order theories.- Generating plans in linear logic.- Automata-theoretic techniques for image generation and compression.- Recognizable infinite tree sets and their complexity.- The expressibility of nondeterministic auxiliary stack automata and its relation to treesize bounded alternating auxiliary pushdown automata.- Towards constructive program derivation in VDM.- A new method for proving termination of AC-rewrite systems.- Efficient parallel algorithms for optical computing with the DFT primitive.- The power of collision: Randomized parallel algorithms for chaining and integer sorting.- Fast parallel algorithms for cographs.- Optimally representing euclidean space discretely for analogically simulating physical phenomena.- Optimal parallel algorithms for testing isomorphism of trees and outerplanar graphs.- Randomized parallel selection.- A fast parallel algorithm for finding a maximal bipartite set.- On the parallel evaluation of classes of circuits.- Voronoi diagrams of moving points in the plane.- Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design.- On some largest empty orthoconvex polygons in a point set.- Defining process fairness for non-interleaving concurrency.- Observational logics and concurrency models.- Distributed reset.- Refinement and composition of transition-based rely-guarantee specifications with auxiliary variables.- Efficient algorithms for crash recovery in distributed systems.- A non-standard inductive semantics.- Relating full abstraction results for different programming languages.- Towards a theory of commonsense visual reasoning.- Natural language processing, complexity theory and logic.