内容

目次

Graphical calculi for interaction.- NP-completeness: A retrospective.- The LEDA platform for combinatorial and geometric computing.- The Wadge-Wagner hierarchy of ?-rational sets.- From chaotic iteration to constraint propagation.- DNA2DNA computations: A potential “killer app”?.- Tilings and quasiperiodicity.- Enumerative sequences of leaves in rational trees.- A completion algorithm for codes with bounded synchronization delay.- The expressibility of languages and relations by word equations.- Finite loops recognize exactly the regular open languages.- An abstract data type for real numbers.- Recursive computational depth.- Some bounds on the computational power of piecewise constant derivative systems (extended abstract).- Monadic simultaneous rigid E-unification and related problems.- Computability on the probability measures on the Borel sets of the unit interval.- Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs.- Results on resource-bounded measure.- Randomization and nondeterminism are comparable for ordered read-once branching programs.- Checking properties of polynomials.- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP.- Game theoretic analysis of call-by-value computation.- On modular properties of higher order extensional lambda calculi.- On explicit substitutions and names (extended abstract).- On the dynamics of sharing graphs.- Minimizing diameters of dynamic trees.- Improving spanning trees by upgrading nodes.- Dynamic algorithms for graphs of bounded treewidth.- The name discipline of uniform receptiveness (extended abstract).- On confluence in the ?-calculus.- A proof theoretical approach to communication.- Solving trace equations using lexicographical normal forms.- Star-free picture expressions are strictly weaker than first-order logic.- An algebra-based method to associate rewards with EMPA terms.- A semantics preserving actor translation.- Periodic and non-periodic min-max equations.- Efficient parallel graph algorithms for coarse grained multicomputers and BSP.- Upper bound on the communication complexity of private information retrieval.- Computation paths logic: An expressive, yet elementary, process logic.- Model checking the full modal mu-calculus for infinite sequential processes.- Symbolic model checking for probabilistic processes.- On the concentration of the height of binary search trees.- An improved master theorem for divide-and-conquer recurrences.- Bisimulation for probabilistic transition systems: A coalgebraic approach.- Distributed processes and location failures.- Basic observables for processes.- Constrained bipartite edge coloring with applications to wavelength routing.- Colouring paths in directed symmetric trees with applications to WDM routing.- On-line routing in all-optical networks.- A complete characterization of the path layout construction problem for ATM networks with given hop count and load.- Efficiency of asynchronous systems and read arcs in petri nets.- Bisimulation equivalence is decidable for one-counter processes.- Symbolic reachability analysis of FIFO-channel systems with nonregular sets of configurations.- Axiomatizations for the perpetual loop in process algebra.- Discrete-time control for rectangular hybrid automata.- Maintaining minimum spanning trees in dynamic graphs.- Efficient splitting and merging algorithms for order decomposable problems.- Efficient array partitioning.- Constructive linear time algorithms for branchwidth.- The word matching problem is undecidable for finite special string-rewriting systems that are confluent.- The geometry of orthogonal reduction spaces.- The theory of vaccines.- The equivalence problem for deterministic pushdown automata is decidable.- On recognizable and rational formal power series in partially commuting variables.- On a conjecture of J. Shallit.- On characterizations of escrow encryption schemes.- Randomness-efficient non-interactive zero knowledge.- Approximation results for the optimum cost chromatic partition problem.- The minimum color sum of bipartite graphs.- A primal-dual approach to approximation of node-deletion problems for matroidal properties.- Independent sets in asteroidal triple-free graphs.- Refining and compressing abstract domains.- Labelled reductions, runtime errors, and operational subsumption.- A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Z m .- Recognizability equals definability for partial k-paths.- Molecular computing, bounded nondeterminism, and efficient recursion.- Constructing big trees from short sequences.- Termination of constraint logic programs.- The expressive power of unique total stable model semantics.