内容

目次

Saturation-based theorem proving (abstract).- Bandwidth efficient parallel computation.- Variable-length maximal codes.- Lower bounds for prepositional proofs and independence results in bounded arithmetic.- Algebraic characterizations of decorated trace equivalences over tree-like structures.- Fast asynchronous systems in dense time.- A hierarchy theorem for the ?-calculus.- An effective tableau system for the linear time ?-calculus.- Characterizing fairness implementability for multiparty interaction.- Termination of context-sensitive rewriting by rewriting.- A complete gentzen-style axiomatization for set constraints.- Fatal errors in conditional expressions.- Different types of arrow between logical frameworks.- Effective models of polymorphism, subtyping and recursion (extended abstract).- Regularity for a large class of context-free processes is decidable.- On infinite transition graphs having a decidable monadic theory.- Semi-groups acting on context-free graphs.- Hard sets method and semilinear reservoir method with applications.- Random polynomials and polynomial factorization.- Optimal gröbner base algorithms for binomial ideals.- Minimum fill-in on circle and circular-arc graphs.- Practical approximation schemes for maximum induced-subgraph problems on K 3,3-free or K 5-free graphs.- Searching a fixed graph.- Improved sampling with applications to dynamic graph algorithms.- The expressive power of existential first order sentences of büchi's sequential calculus.- Fixpoints for rabin tree automata make complementation easy.- New upper bounds to the limitedness of distance automata.- Recognizing regular expressions by means of dataflow networks.- On the power of randomized branching programs.- Hitting sets derandomize BPP.- On type-2 probabilistic quantifiers.- Speeding-up single-tape nondeterministic computations by single alternation, with separation results.- On ?-generators and codes.- On standard Sturmian morphisms.- Constructions and bounds for visual cryptography.- On capital investment.- Lower bounds for static dictionaries on RAMs with bit operations but no multiplication.- Lower bounds for row minima searching.- On the complexity of relational problems for finite state processes.- Deciding finiteness of Petri nets up to bisimulation.- Mobile processes with a distributed environment.- The meaning of negative premises in transition system specifications II.- Average case analyses of list update algorithms, with applications to data compression.- Self-organizing data structures with dependent accesses.- Lopsided trees: Analyses, algorithms, and applications.- Optimal logarithmic time randomized suffix tree construction.- Improved parallel approximation of a class of integer programming problems.- Efficient collective communication in optical networks.- Shared-memory simulations on a faulty-memory DMM.- Fast deterministic backtrack search.- Agent rendezvous: A dynamic symmetry-breaking problem.- Efficient asynchronous consensus with the value-oblivious adversary scheduler.- A formal framework for evaluating heuristic programs.- Improved scheduling algorithms for minsum criteria.- On the complexity of string folding.- A polynomial-time algorithm for near-perfect phylogeny.