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

Alok Aggarwal, Ashok K. Chandra (auth.), Timo Lepistö, Arto Salomaa (eds.)3540194886, 9783540194880

This volume contains the proceedings of ICALP 88, held at Tampere University of Technology, Finland, July 11-15, 1988. ICALP 88 is the 15th International Colloquium on Automata, Languages and Programming in a series of meetings sponsored by the European Association for Theoretical Computer Science (EATCS). It is a broadly based conference covering all aspects of theoretical computer science including topics such as computability, automata, formal languages, analysis of algorithms, computational complexity, data types and data structures, theory of data bases and knowledge bases, semantics of programming languages, program specification, transformation and verification, foundations of logic programming, theory of logical design and layout, parallel and distributed computation, theory of concurrency, symbolic and algebraic computation, term rewriting systems, cryptography, and theory of robotics.

---

Table of contents :
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