8. STACS 1991: Hamburg, Germany

@proceedings{DBLP:conf/stacs/1991,
  editor    = {Christian Choffrut and
               Matthias Jantzen},
  title     = {STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer
               Science, Hamburg, Germany, February 14-16, 1991, Proceedings},
  booktitle = {STACS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {480},
  year      = {1991},
  isbn      = {3-540-53709-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Lectures

• Jacek Leszczylowski, Martin Wirsing: Polymorphism, Parameterization and Typing: An Algebraic Specification Perspective. 1-15 BibTeX
• Jean-Pierre Jouannaud: Executable Higher-Order Algebraic Specifications. 16-25 BibTeX
• Jeffrey Scott Vitter: Efficient Memory Access in Large-Scale Computation. 26-41 BibTeX

Automata and Formal Languages

• Peter Roth: l-Occurrences of Avoidable Patterns. 42-49 BibTeX
• Christiane Frougny, Jacques Sakarovitch: Rational Ralations with Bounded Delay. 50-63 BibTeX
• Martin Schmidt: On the Power of Several Queues. 64-75 BibTeX

Trace Theory

• Giovanna Guaiana, Antonio Restivo, Sergio Salemi: On Aperiodic Trace Languages. 76-88 BibTeX
• Paul Gastin: Recognizable and Rational Languages of Finite and Infinite Traces. 89-104 BibTeX
• Volker Diekert: On the Concatenation of Infinite Traces. 105-117 BibTeX

Algorithms I

• Maria J. Serna, Paul G. Spirakis: Tight RNC Approximations to Max Flow. 118-126 BibTeX
• Michael Godau: A Natural Metric for Curves - Computing the Distance for Polygonal Chains and Approximation Algorithms. 127-136 BibTeX
• 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 BibTeX

Rewriting

• Rémi Gilleron: Decision Problems for Term Rewriting Systems and Recognizable Tree Languages. 148-159 BibTeX
• Klaus Madlener, Friedrich Otto: Decidable Sentences for Context-Free Groups. 160-171 BibTeX

Parallel Models

• Peter Rossmanith: The Owner Concept for PRAMs. 172-183 BibTeX
• Françoise Baude, Guy Vidal-Naquet: Actors as a Parallel Programming Model. 184-195 BibTeX

Logic Programming

• Luc Albert, Rafael Casas, François Fages, A. Torrecillas, Paul Zimmermann: Average Case Analysis of Unification Algorithms. 196-213 BibTeX
• Bal Wang, R. K. Shyamasundar: Methodology for Proving the Termination of Logic Programs. 214-227 BibTeX

Circuits

• Miklos Santha, Christopher B. Wilson: Polynomial Size Constant Depth Circuits with a Limited Number of Negations. 228-237 BibTeX
• Jun Tarui: Randomized Polynomials, Threshold Circuits, and the Polynomial Hierarchy. 238-250 BibTeX

Interactive Proff Systems

• Gilles Brassard, Claude Crépeau, Sophie Laplante, Christian Léger: Computationally Convincing Proofs of Knowledge. 251-262 BibTeX
• Lance Fortnow, Carsten Lund: Interactive Proof Systems and Alternating Time-Space Complexity. 263-274 BibTeX

Distributed Computing

• Bernd Schmeltz: Optimal Tradeoffs Between Time And Bit Complexity In Distributed Synchronous Rings. 275-284 BibTeX
• Birgit Baum-Waidner, Birgit Pfitzmann, Michael Waidner: Unconditional Byzantine Agreement with Good Majority. 285-295 BibTeX
• Svante Carlsson, Christer Mattsson, Patricio V. Poblete, Mats Bengtsson: A New Compacting Garbage-Collection Algorithm with a Good Average-Case Performance. 296-308 BibTeX

Concurrency I

• Walter Vogler: Bisimulation and Action Refinement. 309-321 BibTeX
• Thierry Jéron: Testing for Unboundedness of FIFO Channels. 322-333 BibTeX
• Joffroy Beauquier, Annie Choquet, Antoine Petit, Guy Vidal-Naquet: Detection of Deadlocks in an Infinite Family of Nets. 334-347 BibTeX

Complexity I

• Jonathan F. Buss, Judy Goldsmith: Nondterminism Within P. 348-359 BibTeX
• Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD-Classes. 360-371 BibTeX
• Vladislav Rutenburg: Complexity Classification of Truth Maintenance Systems. 372-383 BibTeX

Concurrency II

• Jörg Desel, Javier Esparza: Reachability in Reversible Free Choice Systems. 384-397 BibTeX
• Eike Best, Ludmila Cherkasova, Jörg Desel: Compositional Generation of Home States in Free Choice Systems. 398-409 BibTeX

Complexity II

• Harry Buhrman, Edith Spaan, Leen Torenvliet: Bounded Reductions. 410-421 BibTeX
• Carme Àlvarez, José L. Balcázar, Birgit Jenner: Functional Oracle Queries as a Measure of Parallel Time. 422-433 BibTeX

Parallel Algorithms

• Gisela Pitsch, Elmar Schömer: Optimal Parallel Recognition of Bracket Languages on Hypercubes. 434-443 BibTeX
• Sanguthevar Rajasekaran, Richard Overholt: Constant Queue Routing on a Mesh. 444-455 BibTeX

Complexity III

• Anne Condon: The Complexity of the Max Word Problem. 456-465 BibTeX
• Erich Grädel: The Expressive Power of Second Order Horn Logic. 466-477 BibTeX

Algorithms II

• Alfredo De Santis, Giuseppe Persiano: Tight Bounds on the Path Length of Binary Trees. 478-487 BibTeX
• Joachim Hartmann: The Random Testability of the n-Input AND Gate. 488-498 BibTeX

Semantics

• Oliver Schoett: An Observational Subset of First-Order Logic Cannot Specify the Behaviour of a Counter (Extended Abstract). 499-510 BibTeX
• François Denis, Jean-Paul Delahaye: Unfolding, Procedural and Fixpoint Semantics of Logic Programs. 511-522 BibTeX
• Philippe Balbiani: A Modal Semantics for the Negation as Failure and the Closed World Assumption Rules. 523-534 BibTeX

Systems

• Rudolf Berghammer, Gunther Schmidt: The RELVIEW-System. 535-536 BibTeX
• E. V. Biryalcev, A. M. Gusenkov, Ildar R. Nasyrov, A. A. Saveliev: Geometry Models Design System GammaPOM. 537-538 BibTeX
• Berthold Hoffmann, Bernd Krieg-Brückner: The PROSPECTRA System. 539-540 BibTeX
• Thierry Jéron: Prototype of a Verification Tool. 541-542 BibTeX
• Jörg Kröger, Lothar Schmitz: IPG - An Interactive Parser Generator. 543-544 BibTeX
• Simone Pimont: A Placement System for Constrained Blocks with Flexible Shapes. 545-546 BibTeX
• D. Rayko, Kirill Vershinin, Igor Romanenko: Algebraic Program Interpreter APREX2. 547-548 BibTeX