8. STACS 1991: Hamburg, Germany
- Christian Choffrut, Matthias Jantzen:
STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, February 14-16, 1991, Proceedings. Lecture Notes in Computer Science 480, Springer 1991, ISBN 3-540-53709-0
Invited Lectures
- Jacek Leszczylowski, Martin Wirsing:
Polymorphism, Parameterization and Typing: An Algebraic Specification Perspective. 1-15
Automata and Formal Languages
Trace Theory
Algorithms I
- Michael Godau:
A Natural Metric for Curves - Computing the Distance for Polygonal Chains and Approximation Algorithms. 127-136 - Ingo Wegener:
The Worst Case Complexity of McDiarmid and Reed's Variant of Bottom-Up-Heap Sort is Less Than n log n + 1.1n. 137-147
Rewriting
- Rémi Gilleron:
Decision Problems for Term Rewriting Systems and Recognizable Tree Languages. 148-159
Parallel Models
Logic Programming
- Luc Albert, Rafael Casas, François Fages, A. Torrecillas, Paul Zimmermann:
Average Case Analysis of Unification Algorithms. 196-213
Circuits
- Miklos Santha, Christopher B. Wilson:
Polynomial Size Constant Depth Circuits with a Limited Number of Negations. 228-237
Interactive Proff Systems
- Gilles Brassard, Claude Crépeau, Sophie Laplante, Christian Léger:
Computationally Convincing Proofs of Knowledge. 251-262 - Lance Fortnow, Carsten Lund:
Interactive Proof Systems and Alternating Time-Space Complexity. 263-274
Distributed Computing
- Bernd Schmeltz:
Optimal Tradeoffs Between Time And Bit Complexity In Distributed Synchronous Rings. 275-284 - Birgit Baum-Waidner, Birgit Pfitzmann, Michael Waidner:
Unconditional Byzantine Agreement with Good Majority. 285-295 - Svante Carlsson, Christer Mattsson, Patricio V. Poblete, Mats Bengtsson:
A New Compacting Garbage-Collection Algorithm with a Good Average-Case Performance. 296-308
Concurrency I
- Joffroy Beauquier, Annie Choquet, Antoine Petit, Guy Vidal-Naquet:
Detection of Deadlocks in an Infinite Family of Nets. 334-347
Complexity I
- Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel:
Structure and Importance of Logspace-MOD-Classes. 360-371
Concurrency II
- Eike Best, Ludmila Cherkasova, Jörg Desel:
Compositional Generation of Home States in Free Choice Systems. 398-409
Complexity II
- Carme Àlvarez, José L. Balcázar, Birgit Jenner:
Functional Oracle Queries as a Measure of Parallel Time. 422-433
Parallel Algorithms
- Gisela Pitsch, Elmar Schömer:
Optimal Parallel Recognition of Bracket Languages on Hypercubes. 434-443
Complexity III
Algorithms II
Semantics
- Oliver Schoett:
An Observational Subset of First-Order Logic Cannot Specify the Behaviour of a Counter (Extended Abstract). 499-510 - François Denis, Jean-Paul Delahaye:
Unfolding, Procedural and Fixpoint Semantics of Logic Programs. 511-522 - Philippe Balbiani:
A Modal Semantics for the Negation as Failure and the Closed World Assumption Rules. 523-534
Systems
- E. V. Biryalcev, A. M. Gusenkov, Ildar R. Nasyrov, A. A. Saveliev:
Geometry Models Design System GammaPOM. 537-538