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