5. STACS 1988: Bordeaux, France

Invited Presentation

• Claus-Peter Schnorr:
  Geometry of Numbers and Integer Programming (Summary). 1-7
  

Algorithms

• Giorgio Gambosi, Giuseppe F. Italiano, Maurizio Talamo:
  Getting Back to the Past in the Union-Find Problem. 8-17
  
• Bernd Becker, Reiner Kolla:
  On the Construction of Optimal Time Adders (Extended Abstract). 18-28
  
• Bettina Just, Friedhelm Meyer auf der Heide, Avi Wigderson:
  On Computations with Integer Division. 29-37
  
• Mark H. Overmars, Michiel H. M. Smid:
  Maintaining Range Trees in Secondary Memory (Extended Abstract). 38-51
  
• David Fernández-Baca, Giora Slutzki:
  Solving Parametric Problems on Trees. 52-60
  
• Walter Unger:
  On the k-Colouring of Circle-Graphs. 61-72
  
• François Bergeron, Gilbert Labelle, Pierre Leroux:
  Functional Equations for Data Structures. 73-80
  

Complexity

• Christoph Meinel:
  The Power of Polynomial Size Omega-Branching Programs. 81-90
  
• Uwe Schöning, Klaus W. Wagner:
  Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries. 91-97
  
• Erich Grädel:
  Domino Games with an Application to the Complexity of Boolean Algebras with Bounded Quantifier Alternations. 98-107
  
• Ingolf Wald:
  An Automatic Speed-up of Random Access Machines with Powerful Arithmetic Instructions. 108-117
  
• Birgit Jenner, Bernd Kirsig:
  Characterizing the Polynomial Hierarchy by Alternating Auxiliary Pushdown Automata. 118-125
  

Formal Languages

• Volker Diekert, Axel Möbus:
  Hotz-Isomorphism Theorems in Formal Language Theory. 126-135
  
• Uschi Heuter:
  First-Order Properties of Trees, Star-Free Expressions, adn Aperiodicity. 136-148
  
• Alain Terlutte:
  Cyclic Rational Transductions and Polynomials of Rational Functions. 149-158
  
• Clelia de Felice:
  Construction of a Family of Finite Maximal Codes. 159-169
  
• Jean-Paul Allouche, Bernard Rande, Loÿs Thimonier:
  Fonctions Génératrices Transcendantes à Coefficients Engendrés par Automates. 170-183
  
• Gilberto Filé:
  The Relation of Two Patterns with Comparable Languages. 184-192
  

Rewriting Systems and Abstract Data Types

• Wadoud Bousdira, Jean-Luc Remy:
  Hierarchical Contextual Rewriting with Several Levels. 193-206
  
• Egidio Astesiano, Alessandro Giovini, Gianna Reggio:
  Generalized Bisimulation in Relational Specifications. 207-226
  

Graph Grammars

• Franz-Josef Brandenburg:
  On Polynomial Time Graph Grammars. 227-236
  
• Bruno Courcelle:
  An Axiomatic Definition of Context-Free Rewriting and its Application to NLC Graph Grammars. 237-247
  

Distributed Algorithms

• Paul G. Spirakis, Basil Tampakas:
  Efficient Distributed Algorithms by Using the Archemedean Time Assumption. 248-263
  
• Martín Abadi, Joan Feigenbaum:
  A Simple Protocol for Secure Circuit Evaluation. 264-272
  
• Guan-Ing Chen, Ten-Hwang Lai:
  Scheduling Independent Jobs on Hypercubes. 273-280
  

Geometrical Algorithms

• Rolf Klein, Derick Wood:
  Voronoi Diagrams Based on General Metrics in the Plane. 281-291
  
• Nicola Santoro, Stuart J. Sidney, Jorge Urrutia:
  Geometric Containment, Common Roots of Polynomials and Partial Orders. 292-300
  
• Pascal Lienhardt:
  Extension of the Notion of Map and Subdivisions of a Three-Dimensional Space. 301-311
  
• Jörg-Rüdiger Sack, Subhash Suri:
  An Optimal Algorithm for Detecting Weak Visibility of a Polygon (Preliminary Version). 312-321
  
• Francis Avnaim, Jean-Daniel Boissonnat:
  Polygon Placement Under Translation and Rotation. 322-333
  

Trace Languages

• Danilo Bruschi, Giovanni Pighizzini, Nicoletta Sabadini:
  On the Existence of the Minimum Asynchronous Automaton and on Decision Problems for Unambiguous Regular Trace Languages. 334-345
  
• Edward Ochmanski:
  On Morphisms of Trace Monoids. 346-355
  

Semantics of Parallelism

• Irène Guessarian, Wafaa Niar-Dinedane:
  An Automaton Characterization of Fairness in SCCS. 356-372
  
• Joost N. Kok:
  A Compositional Semantics for Concurrent Prolog. 373-388
  

Systems Demonstrations

• Patrick Bellot, Remi Legrand:
  Functions and Relations: The GRAAL System. 389-390
  
• Marc V. Benveniste:
  LPC: A Concurrent Programming Laboratory. 391-392
  
• François Bergeron, G. Cartier:
  Darwin: Computer Algebra and Enumerative Combinatorics. 393-394
  
• Thierry Boy de la Tour, Ricardo Caferra, Gilles Chaminade:
  Some Tools for an Inference Laboratory (ATINF). 395-396
  
• Louis Dewez, Jean-Michel Douin, Philippe Lucas:
  MODULOG and the MODULA WorkStation. 397-398
  
• B. Le Goff, Paul Le Guernic:
  The Granules, Blutton: An Idea, an Algorithm to Implement on Multiprocessor. 399-400
  
• Amelia Soriano:
  Prototype de Venus: Un Outil d'Aide à la Verification de Systemes Communicants. 401-402
  
• Egon Wanke:
  PLEXUS: A System for Implementing Hierarchical Graph Algorithms. 403-404