8. STACS 1991: Hamburg, Germany

Invited Lectures

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

Automata and Formal Languages

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

Trace Theory

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

Algorithms I

• Maria J. Serna, Paul G. Spirakis:
  Tight RNC Approximations to Max Flow. 118-126
  
• 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
  
• Klaus Madlener, Friedrich Otto:
  Decidable Sentences for Context-Free Groups. 160-171
  

Parallel Models

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

Logic Programming

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

Circuits

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

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

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

Complexity I

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

Concurrency II

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

Complexity II

• Harry Buhrman, Edith Spaan, Leen Torenvliet:
  Bounded Reductions. 410-421
  
• 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
  
• Sanguthevar Rajasekaran, Richard Overholt:
  Constant Queue Routing on a Mesh. 444-455
  

Complexity III

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

Algorithms II

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

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

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