6. STACS 1989: Paderborn, Germany

@proceedings{DBLP:conf/stacs/1989,
  editor    = {Burkhard Monien and
               Robert Cori},
  title     = {STACS 89, 6th Annual Symposium on Theoretical Aspects of Computer
               Science, Paderborn, FRG, February 16-18, 1989, Proceedings},
  booktitle = {STACS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {349},
  year      = {1989},
  isbn      = {3-540-50840-6},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Presentations

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

Semantics 1

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

Computational Geometry

• Panagiotis Alevizos, Jean-Daniel Boissonnat, Franco P. Preparata: On the Boundary of a Union of Rays. 72-83 BibTeX
• Franco P. Preparata, Roberto Tamassia: Dynamic Planar Point Location with Optimal Query Time. 84-95 BibTeX
• 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 BibTeX

Structures

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

Automata Theory

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

Parallel Algorithms

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

Complexity 1

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

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 BibTeX , journal version: Theor. Comput. Sci. 74(1): 115-119(1990) BibTeX
• Piotr Berman, Georg Schnitger: On the Complexity of Approximating the Independent Set Problem. 256-268 BibTeX

Distributed Computing

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

Fault Tolerance

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

Semantics 2

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

Completeness

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

Concurrency

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

Formal Languages

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

Graph Algorithms

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

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 BibTeX
• Michael Himsolt: Graph^Ed: An Interactive Garpg Editor. 532-533 BibTeX
• M. Jäger: SAMPLE: A Language Dependent Prototyping Environment. 534-535 BibTeX
• Tomasz Janowski: Examining the Satisfiability of Formulas of Propositional Dynamic Logic. 536 BibTeX
• V. Kell, Albert Maier, Andreas Potthoff, Wolfgang Thomas, U. Wermuth: AMORE: A System for Computing Automata, MOnoidsm and Regular Expressions. 537-538 BibTeX
• Olov Schelén, N. O. Forsgren: A Proof System for Type Theory and CCS. 539-540 BibTeX
• Thomas Wolff: Implementation of a Transition Sematics for Parallel Programs with Shared Variables. 541-543 BibTeX