Automata, Languages and Programming -

. .

Sommaire:
Communication complexity of PRAMs.- Average case complexity analysis of the RETE multi-pattern match algorithm.- Problems easy for tree-decomposable graphs extended abstract.- Serializability in distributed systems with handshaking.- Algorithms for planar geometric models.- Nonuniform learnability.- Zeta functions of recognizable languages.- Dynamic programming on graphs with bounded treewidth.- Efficient simulations of simple models of parallel computation by time-bounded ATM's and space-bounded TM's.- Optimal slope selection.- Approximation of a trace, asynchronous automata and the ordering of events in a distributed system.- New techniques for proving the decidability of equivalence problems.- Transitive orientations, m?bius functions, and complete semi-thue systems for free partially commutative monoids.- The complexity of matrix transposition on one-tape off-line turing machines with output tape.- Geometric structures in computational geometry.- Arrangements of curves in the plane - topology, combinatorics, and algorithms.- Reset sequences for finite automata with application to design of parts orienters.- Random allocations and probabilistic languages.- Systolic architectures, systems and computations.- New developments in structural complexity theory.- Operational semantics of OBJ-3.- Do we really need to balance patricia tries?.- Contractions in comparing concurrency semantics.- A complexity theory of efficient parallel algorithms.- On the learnability of DNF formulae.- Efficient algorithms on context-free graph languages.- Efficient analysis of graph properties on context-free graph languages.- A polynomial-time algorithm for subgraph isomorphism of two-connected series-parallel graphs.- Constructive Hopf's theorem: Or how to untangle closed planar curves.-Maximal dense intervals of grammar forms.- Computations, residuals, and the power of indeterminacy.- Nested annealing: A provable improvement to simulated annealing.- Nonlinear pattern matching in trees.- Invertibility of linear finite automata over a ring.- Moving discs between polygons.- Optimal circuits and transitive automorphism groups.- A Kleene-presburgerian approach to linear production systems.- On minimum flow and transitive reduction.- La Reconnaissance Des Facteurs D'un Langage Fini Dans Un Texte En Temps Lineaire - Resume -.- Regular languages defined with generalized quantifiers.- A dynamic data structure for planar graph embedding.- Separating polynomial-time turing and truth-table reductions by tally sets.- Assertional verification of a timer based protocol.- Type inference with partial types.- Some behavioural aspects of net theory.- The equivalence of dgsm replications on Q-rational languages is decidable.- Pfaffian orientations, 0/1 permanents, and even cycles in directed graphs.- On restricting the access to an NP-oracle.- On ? 1?tt p -sparseness and nondeterministic complexity classes.- Semantics for logic programs without occur check.- Outer narrowing for equational theories based on constructors.