Automata, Languages and Programming

Prof. Dr. Thomas Ottmann, Institut für Informatik, Universität Freiburg.

Probability and plurality for aggregations of learning machines.- Logic programming with ions.- Inverse image analysis.- A unification algorithm for confluent theories.- On the Knuth-Bendix completion for concurrent processes.- On word problems in equational theories.- Semantics for nondeterministic asynchronous broadcast networks.- Another look at abstraction in process algebra.- A timed failures model for extended communicating processes.- Readiness semantics for regular processes with silent actions.- Verifying a protocol using relativized bisimulation.- On recent trends in formal language theory.- Non-uniform automata over groups.- Minimal automaton of a rational cover.- A star-height problem in free monoids with partial commutations.- Single-valued finite transduction.- The kleene and the Parikh Theorem in complete semirings.- An algorithm for computing asynchronous automata in the case of acyclic non-commutation graphs.- On the languages accepted by finite reversible automata.- Decision problems for regular trace languages.- Panic mode without panic.- Computation tree logic CTL* and path quantifiers in the monadic theory of the binary tree.- Modelchecking of CTL formulae under liveness assumptions.- A modal logic for a subclass of event structures.- Parallel 5-colouring of planar graphs.- Parallel construction of a suffix tree.- The probabilistic and deterministic parallel complexity of symmetric functions.- Term matching on parallel computers.- Guessing games and distributed computations in synchronous networks.- On the bivariate function minimization problem and its applications to motion planning.- Testing the necklace condition for Shortest Tours and optimal factors in the plane.- Nearly optimal heuristics for binary search trees with geometric generalizations.- Approximating integer lattices by lattices with cyclic factor groups.- On the complexity of graph critical uncolorability.- Posets, boolean representations and quick path searching.- The lexicographically first maximal subgraph problems: P-completeness and NC algorithms.- Uniform computational complexity of Taylor series.- Efficient on-line algorithms for the knapsack problem.- Lower bounds for sorting of sums.- The I/O complexity of sorting and related problems.- A lower bound for the complexity of the Union-Split-Find problem.- The nearest common ancestor in a dynamic tree.- A generalization of the procedure of karp and miller to well structured transition systems.- Completeness results for reachability, containment, and equivalence, with respect to conflict-free vector replacement systems.- Partial algebras flow from algebraic specifications.- The logarithmic alternation hierarchy collapses: $$ASigma _2^mathcal{L} = APi _2^mathcal{L}$$ .- Testing membership in commutative transformation semigroups.- On the computing power of one-way cellular arrays.- Recent developments in the theory of learning.