STACS 91: 8th Annual Symposium on Theoretical Aspects of Computer Science Hamburg, Germany, February 14–16, 1991 Proceedings

Jacek Leszczylowski, Martin Wirsing (auth.), Christian Choffrut, Matthias Jantzen (eds.)3540537090, 9783540537090

This volume contains the proceedings of STACS 91, a symposium on the theoretical aspects of computer science, held in Hamburg, Germany in February 1991. STACS is held each year, alternately in Germany and France, and is organized jointly by the Special Interest Group for Theoretical Computer Science of the Gesellschaft fuer Informatik (GI) and the Special Interest Group for Applied Mathematics of the Association Francaise des Sciences et Techniques de l’Information et de Systemes (AFCET). The topics covered in this volume include abstract data types, algorithms and data structures, automata and formal languages, complexity of concrete algorithms, computational geometry, cryptography, computer systems theory, logic and semantics, mathematics of computation, program specification, theory of parallel and distributed computation, structural complexity, theory of robotics, VLSI structures, and the theory of databases.

---

Table of contents :
Polymorphism, parameterization and typing: An algebraic specification perspective….Pages 1-15
Executable higher-order algebraic specifications….Pages 16-25
Efficient memory access in large-scale computation….Pages 26-41
l -occurrences of avoidable patterns….Pages 42-49
Rational relations with bounded delay….Pages 50-63
On the power of several queues….Pages 64-75
On aperiodic trace languages….Pages 76-88
Recognizable and rational languages of finite and infinite traces….Pages 89-104
On the concatenation of infinite traces….Pages 105-117
Tight RNC approximations to Max Flow….Pages 118-126
A natural metric for curves — Computing the distance for polygonal chains and approximation algorithms….Pages 127-136
The worst case complexity of MC Diarmid and Reed’s variant of BOTTOM-UP-HEAT SORT is less than n log n+1.1n….Pages 137-147
Decision problems for term rewriting systems and recognizable tree languages….Pages 148-159
Decidable sentences for context-free groups….Pages 160-171
The owner concept for PRAMs….Pages 172-183
Actors as a parallel programming model….Pages 184-195
Average case analysis of unification algorithms….Pages 196-213
Methodology for proving the termination of logic programs….Pages 214-227
Polynomial size constant depth circuits with a limited number of negations….Pages 228-237
Randomized polynomials, threshold circuits, and the polynomial hierarchy….Pages 238-250
Computationally convincing proofs of knowledge….Pages 251-262
Interactive proof systems and alternating time-space complexity….Pages 263-274
Optimal tradeoffs between time and bit complexity in distributed synchronous rings….Pages 275-284
Unconditional Byzantine Agreement with good majority….Pages 285-295
A new compacting garbage-collection algorithm with a good average-case performance….Pages 296-308
Bisimulation and action refinement….Pages 309-321
Testing for unboundedness of Fifo channels….Pages 322-333
Detection of deadlocks in an infinite family of nets….Pages 334-347
Nondeterminism within P ….Pages 348-359
Structure and importance of logspace-MOD-classes….Pages 360-371
Complexity classification of Truth Maintenance systems….Pages 372-383
Reachability in reversible Free Choice systems….Pages 384-397
Compositional generation of home states in free choice systems….Pages 398-409
Bounded reductions….Pages 410-421
Functional oracle queries as a measure of parallel time….Pages 422-433
Optimal parallel recognition of bracket languages on hypercubes….Pages 434-443
Constant queue routing on a mesh….Pages 444-455
The complexity of the max word problem….Pages 456-465
The expressive power of second order Horn logic….Pages 466-477
Tight bounds on the path length of binary trees….Pages 478-487
The random testability of the n -input AND gate….Pages 488-498
An observational subset of first-order logic cannot specify the behaviour of a counter (extended abstract)….Pages 499-510
Unfolding, procedural and fixpoint semantics of logic programs….Pages 511-522
A modal semantics for the negation as failure and the closed world assumption rules….Pages 523-534
The relview-system….Pages 535-536
Geometry models design system ΓPOM….Pages 537-538
The prospectra system….Pages 539-540
Prototype of a verification tool….Pages 541-542
IPG — An interactive parser generator….Pages 543-544
A placement system for constrained blocks with flexible shapes….Pages 545-546
Algebraic programm interpreter APREX2….Pages 547-548