Automata, Languages and Programming

Theory of 2-structures.- A domain for concurrent termination a generalization of Mazurkiewicz traces.- Nonfinite axiomatizability of the equational theory of shuffle.- The algebraic equivalent of AFL theory.- Finite state transformations of images.- Post correspondence problem: Words possible as primitive solutions.- Computing the closure of sets of words under partial commutations.- Intervalizing k-colored graphs.- NC algorithms for finding a maximal set of paths with application to compressing strings.- On the construction of classes of suffix trees for square matrices: Algorithms and applications.- How to use the minimal separators of a graph for its chordal triangulation.- Fast gossiping by short messages.- Break Finite Automata Public Key Cryptosystem.- Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time.- On the number of random bits in totally private computation.- Lower time bounds for randomized computation.- New collapse consequences of NP having small circuits.- The complexity of searching succinctly represented graphs.- Optimal shooting: Characterizations and applications.- Placing resources in a tree: Dynamic and static algorithms.- Shortest path queries in digraphs of small treewidth.- A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs.- Parallel algorithms with optimal speedup for bounded treewidth.- Approximating minimum cuts under insertions.- Linear time algorithms for dominating pairs in asteroidal triple-free graphs.- On-line resource management with applications to routing and scheduling.- Alternation in simple devices.- Hybrid automata with finite bisimulations.- Generalized Sturmian languages.- Polynomial closure and unambiguous product.- Lower bounds on algebraic random access machines.- Improved deterministic PRAM simulation on the mesh.- On optimal polynomial time approximations: P-levelability vs. ?-levelability.- Weakly useful sequences.- Graph