6. STACS 1989: Paderborn, Germany

Invited Presentations

• Friedhelm Meyer auf der Heide:
  On Genuinely Time Bounded Compuations. 1-16
  
• Peter D. Mosses:
  Unified Algebras and Action Semantics. 17-35
  
• Jean Berstel:
  Properties of Infinite Words: Recent Result. 36-46
  

Semantics 1

• Francisca Lucio-Carrasco, Antonio Gavilanes-Franco:
  A First Order Logic for Partial Functions (Extended Abstract). 47-58
  
• Rolf Hennicker:
  Observational Implementations. 59-71
  

Computational Geometry

• Panagiotis Alevizos, Jean-Daniel Boissonnat, Franco P. Preparata:
  On the Boundary of a Union of Rays. 72-83
  
• Franco P. Preparata, Roberto Tamassia:
  Dynamic Planar Point Location with Optimal Query Time. 84-95
  
• Hristo Djidjev, Andrzej Lingas, Jörg-Rüdiger Sack:
  An O(n log n) Algorithm for Computing a Link Center in a Simple Polygon. 96-107
  

Structures

• Wolfgang Gutjahr, Emo Welzl, Gerhard J. Woeginger:
  Polynomial Graph-Colorings. 108-119
  
• Friedhelm Meyer auf der Heide, Rolf Wanka:
  Time-Optimal Simulations of Networks by Universal Parallel Computers. 120-131
  
• Friedhelm Hinz:
  Classes of Picture Languages that Cannot be Distinguished in the Chain Code Concept and Deletion of Redundant Retreats. 132-143
  

Automata Theory

• Christiane Frougny:
  Linear Numeration Systems, Theta-Developments and Finite Automata. 144-155
  
• Jeffrey Shallit:
  A Generalization of Automatic Sequences. 156-167
  
• Volker Diekert:
  Word Problems over TRaces Which are Solvable in Linear Time. 168-180
  

Parallel Algorithms

• Friedhelm Meyer auf der Heide:
  Computing Minimum Spanning Forests on 1- and 2-Dimensional Processor Arrays. 181-192
  
• Otfried Schwarzkopf:
  Parallel Computation of Discrete Voronoi Diagrams (Extended Abstract). 193-204
  
• Donald S. Fussell, Ramakrishna Thurimella:
  Successive Approximation in Parallel Graph Algorithms. 205-217
  

Complexity 1

• Gerhard Buntrock, Albrecht Hoene:
  Reversals and Alternation. 218-228
  
• Jin-yi Cai, Lane A. Hemachandra:
  On the Power of Parity Polynomial Time. 229-239
  
• K. Ganesan, Steven Homer:
  Complete Problems and Strong Polynomial Reducibilities. 240-250
  

Complexity 2

• Andrzej Szepietowski: If Deterministic and Nondeterministic Space Complexities are Equal for log log n then they are also Equal for log n. 251-255 , journal version: Theor. Comput. Sci. 74(1): 115-119(1990)
• Piotr Berman, Georg Schnitger:
  On the Complexity of Approximating the Independent Set Problem. 256-268
  

Distributed Computing

• Christian Lavault:
  Average Number of Messages for Distributed Leader Finding in Rings of Processors. 269-281
  
• Mark H. Overmars, Nicola Santoro:
  TIME vs BITS. 282-293
  
• Paul Beame, Hans L. Bodlaender:
  Distributed Computing on TRansitive Networks: The Thorus. 294-303
  

Fault Tolerance

• Nicola Santoro, Peter Widmayer:
  Time is Not a Healer. 304-313
  
• Rüdiger Reischuk, Bernd Schmeltz:
  Area Efficient Methods to Increase the Reliability of Combinatorial Circuits. 314-326
  
• Jürgen Doenhardt:
  Fault Masking Probabilities with Single and Multiple Signature Analysis. 327-338
  

Semantics 2

• Miki Hermann:
  Chain Properties of Rule Closures. 339-347
  
• Paliath Narendran, Jonathan Stillman:
  It is Undecidable Whether the Knuth-Bendix Completion Procedure Generates a Crossed Pair. 348-359
  
• Friederike Nickl:
  Algebraic Specifications for Domain THeory. 360-374
  
• Aïda Batarekh, V. S. Subrahmanian:
  The Query Topology in Logic Programming. 375-387
  

Completeness

• Martin Beaudry, Pierre McKenzie, Denis Thérien:
  Testing Membership: Beyond Permutation Groups (Extended Abstract). 388-399
  
• Ernst W. Mayr:
  Membership in Plynomial Ideals over Q Is Exponential Space Complete. 400-406
  
• Rakesh M. Verma, I. V. Ramakrishnan:
  Some Complexity Theoretic Aspects of AC Rewriting. 407-420
  

Concurrency

• Bengt Jonsson, Joachim Parrow:
  Deciding Bisimulation Equivalences for a Class of Non-Finite-State Programs. 421-433
  
• Bernadette Charron-Bost:
  Measure of Parallelism of Distributed Computations. 434-445
  
• Petr Jancar:
  Decidability of Waek Fairness in Petri Nets. 446-457
  

Formal Languages

• Jean-Eric Pin, Howard Straubing, Denis Thérien:
  New Results on the Generalized Star-Height Problem. 458-467
  
• Karel Culik II, Juhani Karhumäki:
  On the Equivalence Problem for Deterministic Multitape Automata and Transducers. 468-479
  
• Helmut Seidl:
  Deciding Equivalence of Finite Tree Automata. 480-492
  

Graph Algorithms

• Marc J. van Kreveld, Mark H. Overmars:
  Concatenable Segment Trees (Extended Abstract). 493-504
  
• Andreas Schwill:
  Shorest Edge-Disjoint Paths in Graphs. 505-516
  
• Bala Kalyanasundaram, Georg Schnitger:
  Rounds versus Time for the Two Person Pebble Game (Extended Abstract). 517-529
  

Systems

• Maria Morandi Cecchi, F. Nachria, O. Viele:
  AXE: The Syntax Driven Diagram Editor for Visual Languages used in the Software Engineering Environments AxIS. 530-531
  
• Michael Himsolt:
  Graph^Ed: An Interactive Garpg Editor. 532-533
  
• M. Jäger:
  SAMPLE: A Language Dependent Prototyping Environment. 534-535
  
• Tomasz Janowski:
  Examining the Satisfiability of Formulas of Propositional Dynamic Logic. 536
  
• V. Kell, Albert Maier, Andreas Potthoff, Wolfgang Thomas, U. Wermuth:
  AMORE: A System for Computing Automata, MOnoidsm and Regular Expressions. 537-538
  
• Olov Schelén, N. O. Forsgren:
  A Proof System for Type Theory and CCS. 539-540
  
• Thomas Wolff:
  Implementation of a Transition Sematics for Parallel Programs with Shared Variables. 541-543