Foundations of Software Technology and Theoretical Computer Science

Efficient resolution of singularities of plane curves.- On the interactive complexity of graph reliability.- Matching upper and lower bounds for simulations of several tapes on one multidimensional tape.- The complexity of computing over quasigroups.- Non-commutative computation, depth reduction, and skew circuits (extended abstract).- Inductive definitions and type theory an introduction (preliminary version).- Interpreter verification for a functional language.- An epistemic foundation for logic programming with uncertainty.- On typed calculi with a merge operator.- Incremental algorithms for the single-source shortest path problem.- An O(n) algorithm for realizing degree sequences.- Coloring semi-random graphs in polynomial expected time.- Finite-state strategies in regular infinite games.- Location of the largest empty rectangle among arbitrary obstacles.- Efficient parallel and linear time sequential split decomposition (extended abstract).- Algorithms for convex visibility problems.- Lower bounds for parallel algebraic decision trees, complexity of convex hulls and related problems.- Localities and failures (extended summary).- Priority and abstraction in process algebra.- On the computational power of operators in ICSP with fairness.- Decidability of timed language-inclusion for networks of real-time communicating sequential processes.- My favorite ten complexity theorems of the past decade.- Solving a unification problem under constrained substitutions using tree automata.- Automata-driven efficient subterm unification.- Randomized approximation algorithms in combinatorial optimization.- A limited-backtrack greedy schema for approximation algorithms.- On approximation scheme preserving reductibility and its applications.- Approximation schemes using L-reductions.- An explanation of splaying.- Proving non-reachability by modulo-place-invariants.- Soundness and completeness of UNITY logic.- Efficient algorithms for the transformation between different types of binary decision diagrams.- Extending the limits of sequentially phased reasoning.- Foundations for faster external sorting.- Branching rules for satisfiability.- Using linear arithmetic procedure for generating induction schemes.