Automata, Languages and Programming: 15th International Colloquium Tampere, Finland, July 11–15, 1988 Proceedings

Communication complexity of PRAMs....Pages 1-17
Average case complexity analysis of the RETE multi-pattern match algorithm....Pages 18-37
Problems easy for tree-decomposable graphs extended abstract....Pages 38-51
Serializability in distributed systems with handshaking....Pages 52-66
Algorithms for planar geometric models....Pages 67-81
Nonuniform learnability....Pages 82-92
Zeta functions of recognizable languages....Pages 93-104
Dynamic programming on graphs with bounded treewidth....Pages 105-118
Efficient simulations of simple models of parallel computation by time-bounded ATM's and space-bounded TM's....Pages 119-132
Optimal slope selection....Pages 133-146
Approximation of a trace, asynchronous automata and the ordering of events in a distributed system....Pages 147-161
New techniques for proving the decidability of equivalence problems....Pages 162-175
Transitive orientations, möbius functions, and complete semi-thue systems for free partially commutative monoids....Pages 176-187
The complexity of matrix transposition on one-tape off-line turing machines with output tape....Pages 188-200
Geometric structures in computational geometry....Pages 201-213
Arrangements of curves in the plane — topology, combinatorics, and algorithms....Pages 214-229
Reset sequences for finite automata with application to design of parts orienters....Pages 230-238
Random allocations and probabilistic languages....Pages 239-253
Systolic architectures, systems and computations....Pages 254-270
New developments in structural complexity theory....Pages 271-286
Operational semantics of OBJ-3....Pages 287-301
Do we really need to balance patricia tries?....Pages 302-316
Contractions in comparing concurrency semantics....Pages 317-332
A complexity theory of efficient parallel algorithms....Pages 333-346
On the learnability of DNF formulae....Pages 347-361
Efficient algorithms on context-free graph languages....Pages 362-378
Efficient analysis of graph properties on context-free graph languages....Pages 379-393
A polynomial-time algorithm for subgraph isomorphism of two-connected series-parallel graphs....Pages 394-409
Constructive Hopf's theorem: Or how to untangle closed planar curves....Pages 410-423
Maximal dense intervals of grammar forms....Pages 424-438
Computations, residuals, and the power of indeterminacy....Pages 439-454
Nested annealing: A provable improvement to simulated annealing....Pages 455-472
Nonlinear pattern matching in trees....Pages 473-488
Invertibility of linear finite automata over a ring....Pages 489-501
Moving discs between polygons....Pages 502-515
Optimal circuits and transitive automorphism groups....Pages 516-524
A Kleene-presburgerian approach to linear production systems....Pages 525-534
On minimum flow and transitive reduction....Pages 535-546
La Reconnaissance Des Facteurs D'un Langage Fini Dans Un Texte En Temps Lineaire - Resume -....Pages 547-560
Regular languages defined with generalized quantifiers....Pages 561-575
A dynamic data structure for planar graph embedding....Pages 576-590
Separating polynomial-time turing and truth-table reductions by tally sets....Pages 591-599
Assertional verification of a timer based protocol....Pages 600-614
Type inference with partial types....Pages 615-629
Some behavioural aspects of net theory....Pages 630-653
The equivalence of dgsm replications on Q-rational languages is decidable....Pages 654-666
Pfaffian orientations, 0/1 permanents, and even cycles in directed graphs....Pages 667-681
On restricting the access to an NP-oracle....Pages 682-696
Semantics for logic programs without occur check....Pages 697-709
Outer narrowing for equational theories based on constructors....Pages 710-726
....Pages 727-741