Automata, Languages and Programming

Algorithmic verification of linear temporal logic specifications.- On existentially first-order definable languages and their relation to NP.- An algebraic approach to communication complexity.- Deciding global partial-order properties.- Simple linear-time algorithms for minimal fixed points.- Hardness results for dynamic problems by extensions of Fredman and Saks' chronogram method.- Simpler and faster dictionaries on the AC0 RAM.- Partial-congruence factorization of bisimilarity induced by open maps.- Reset nets between decidability and undecidability.- Geometric algorithms for robotic manipulation.- Compact encodings of planar graphs via canonical orderings and multiple parentheses.- Reducing simple polygons to triangles - A proof for an improved conjecture -.- Difficult configurations - on the complexity of LTrL.- On the expressiveness of real and integer arithmetic automata.- Distributed matroid basis completion via elimination upcast and distributed correction of minimum-weight spanning trees.- Independent sets with domination constraints.- Robust asynchronous protocols are finite-state.- Deciding bisimulation-like equivalences with finite-state processes.- Do probabilistic algorithms outperform deterministic ones?.- A degree-decreasing Lemma for (MOD q, MOD p) circuits.- Improved pseudorandom generators for combinatorial rectangles.- Translation validation for synchronous languages.- An efficient and unified approach to the decidability of equivalence of propositional programs.- On branching programs with bounded uncertainty.- CONS-free programs with tree input.- Concatenable graph processes: Relating processes and derivation traces.- Axioms for contextual net processes.- Existential types: Logical relations and operational equivalence.- Optimal samplingstrategies in quicksort.- A genuinely polynomial-time algorithm for sampling two-rowed contingency tables.- A modular approach to denotational semantics.- Generalised flowcharts and games.- Efficient minimization of numerical summation errors.- Efficient approximation algorithms for the subset-sums equality problem.- Structural recursive definitions in type theory.- A good class of tree automata. Application to inductive theorem proving.- Locally periodic infinite words and a chaotic behaviour.- Bridges for concatenation hierarchies.- Complete proof systems for observation congruences in finite-control ?-calculus.- Concurrent constraints in the fusion calculus.- On computing the entropy of cellular automata.- On the determinization of weighted finite automata.- Bulk-synchronous parallel multiplication of boolean matrices.- A complex example of a simplifying rewrite system.- On a duality between Kruskal and Dershowitz theorems.- A total AC-compatible reduction ordering on higher-order terms.- Model checking game properties of multi-agent systems.- Limited wavelength conversion in all-optical tree networks.- Computing mimicking networks.- Metric semantics for true concurrent real time.- The regular real-time languages.- Static and dynamic low-congested interval routing schemes.- Low-bandwidth routing and electrical power networks.- Constraint automata and the complexity of recursive subtype entailment.- Reasoning about the past with two-way automata.- A neuroidal architecture for cognitive computation.- Deterministic polylog approximation for minimum communication spanning trees.- A polynomial time approximation scheme for euclidean minimum cost k-connectivity.- Global/local subtyping and capability inference for a distributed ?-calculus.- Checking strong/Weakbisimulation equivalences and observation congruence for the ?-calculus.- Inversion of circulant matrices over Zm.- Application of Lempel-Ziv encodings to the solution of word equations.- Explicit substitutitions for constructive necessity.- The relevance of proof-irrelevance.- New horizons in quantum information processing.- Sequential iteration of interactive arguments and an efficient zero-knowledge argument for NP.- Image density is complete for non-interactive-SZK.- Randomness spaces.- Totality, definability and boolean circuits.- Quantum counting.- On the complexity of deriving score functions from examples for problems in molecular biology.- A hierarchy of equivalences for asynchronous calculi.- On asynchrony in name-passing calculi.- Protection in programming-language translations.- Efficient simulations by queue machines.- Power of cooperation and multihead finite systems.- A simple solution to type specialization.- Multi-stage programming: axiomatization and type safety.