Automata, Languages and Programming

Program result checking: A new approach to making programs more reliable.- Dynamic interpolation search in o(log log n) time.- Searching among intervals and compact routing tables.- The approximation of maximum subgraph problems.- Polynomially bounded minimization problems which are hard to approximate.- Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover.- The complexity of approximating PSPACE-complete problems for hierarchical specifications.- Problems on pairs of trees and the four colour problem of planar graphs.- Constructing competitive tours from local information.- Treewidth and pathwidth of permutation graphs.- A theory of even functionals and their algorithmic applications.- Exact asymptotics of divide-and-conquer recurrences.- Optimal bounds for the change-making problem.- The complexity of N-body simulation.- A simple method for resolving degeneracies in Delaunay triangulations.- Fault-tolerance and complexity (Extended abstract).- Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines.- On the computational power of discrete Hopfield nets.- On randomized versus deterministic computation.- Lower bounds for one-way probabilistic communication complexity.- Maintaining discrete probability distributions optimally.- Secure and efficient off-line digital money (extended abstract).- Computational depth and reducibility.- Learnability: Admissible, co-finite, and hypersimple languages.- Inclusion is undecidable for pattern languages.- New decidability results concerning two-way counter machines and applications.- Cobham's Theorem seen through Büchi's Theorem.- Logical definability on infinite traces.- Algebras for classifying regular tree languages and an application to frontier testability.- Finite automata as characterizations of minor closed tree families (extended abstract).- On distributed algorithms in a broadcast domain.- Sparse networks