Automata, Languages, and Programming

Unexpected upper bounds on the complexity of some communication games.- Valuations and unambiguity of languages, with applications to fractal geometry.- On the computational power of probabilistic and faulty neural networks.- Deciding properties of integral relational automata.- On the cost of recomputing: tight bounds on pebbling with faults.- On some relations between dynamical systems and transition systems.- Complexity results for multi-pebble automata and their logics.- An analysis of the Core-ML language: Expressive power and type reconstruction.- Expressiveness of efficient semi-deterministic choice constructs.- Tailoring recursion for complexity.- Determinizing asynchronous automata.- On the complementation of Büchi asynchronous cellular automata.- Distribution and locality of concurrent systems.- Liveness in timed and untimed systems.- Average-case analysis of pattern-matching in trees under the BST probability model.- On the approximation of shortest common supersequences and longest common subsequences.- Optimal parallel algorithms for Prefix Matching.- Optimal two-dimensional compressed matching.- Maintaining spanning trees of small diameter.- Simple fast parallel hashing.- The Optimal Alphabetic Tree problem revisited.- On the cutting edge of relativization: The resource bounded injury method.- PSPACE-completeness of certain algorithmic problems on the subgroups of free groups.- Higher-order processes and their models.- Efficient local correctness checking for single and alternating boolean equation systems.- Undecidable verification problems for programs with unreliable channels.- Reasoning about programs by exploiting the environment.- A model of intuitionistic affine logic from stable domain theory.- Bistructures, bidomains and linear logic.-Equivalences for fair Kripke structures.- Generalizing finiteness conditions of labelled transition systems.- A kleene theorem for recognizable languages over concurrency monoids.- Least solutions of equations over N.- Fast uniform analysis of Coupled-Context-Free languages.- Polynomial closure of group languages and open sets of the Hall topology.- Pumping, cleaning and symbolic constraints solving.- Dynamically-typed computations for order-sorted equational presentations.- Combining first order algebraic rewriting systems, recursion and extensional lambda calculi.- On the theory of interconnection networks for parallel computers.- Multiway cuts in directed and node weighted graphs.- A fast randomized LOGSPACE algorithm for graph connectivity.- Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing.- The size of an intertwine.- Finding even cycles even faster.- Polynomial time analysis of toroidal periodic graphs.- A tight lower bound for primitivity in k-structures.- Randomness in distribution protocols.- Lower space bounds for randomized computation.- The average case complexity of the parallel prefix problem.- Prefix codes: Equiprobable words, unequal letter costs.- A super-logarithmic lower bound for hypercubic sorting networks.- Efficient strategies for robot navigation in unknown environment.