Foundations of Software Technology and Theoretical Computer Science

Program checking.- Randomizing reductions of search problems.- Time analysis, cost equivalence and program refinement.- AC-equation solving.- On the operational interpretation of complex types.- Tense logics for local reasoning in distributed systems.- Failures semantics for a simple process language with refinement.- Correctness of programs over poor signatures.- Complexity issues for vacillatory function identification.- A purely algebraic proof of McNaughton's theorem on infinite words.- The structure and complexity of minimal NFA's over a unary alphabet.- Relativised cellular automata and complexity classes.- Computing the order of a locally testable automaton.- On the structure and complexity of infinite sets with minimal perfect hash functions.- NP-hard sets and creativeness over constant time languages.- Complete problems involving boolean labelled structures and projection translations.- Is BP.? $$\mathcal{P}$$ a probabilistic class?.- Fast stable in-place sorting with O(n) data moves.- A theorem on the approximation of set cover and vertex cover.- A fast algorithm for the principal partition of a graph.- Uniform circuits and exclusive read PRAMs.- Contracting planar graphs efficiently in parallel.- Fast deterministic selection on mesh-connected processor arrays.- Improved selection in totally monotone arrays.- Designing secure communication protocols from trust specifications.- Computing the shortest path tree in a weak visibility polygon.- Usefulness of angle-sweep over line-sweep.- Petri nets and transition systems (Abstract for an invited talk).