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

---

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