STACS 89 6th Annual Symposium on Theoretical Aspects of Computer Science, Paderborn, FRG, February 16-18, 1989; Proceedings

This volume contains the presentations of the Sixth Symposium on Theoretical Aspects of Computer Science (STACS 89) held at the University of Paderborn, February 16-18, 1989. In addition to papers presented in the regular program the volume contains abstracts of software systems demonstrations which were included in this conference series in order to show applications of research results in theoretical computer science. The papers are grouped into the following thematic sections: computational geometry, automata theory and formal languages, semantics of programming languages, parallel algorithms, graph algorithms, complexity, structures, fault tolerance, completeness, distributed computing and concurrency.

On genuinely time bounded computations.- Unified Algebras and action semantics.- Properties of infinite words : Recent results.- A first order logic for partial functions.- Observational implementations.- On the boundary of a union of Rays.- Dynamic planar point location with optimal query time.- An O(n log n) algorithm for computing a link center in a simple polygon.- Polynomial graph-colorings.- Time-optimal simulations of networks by universal parallel computers.- Classes of picture languages that cannot be distinguished in the chain code concept and deletion of redundant retreats.- Linear numeration systems, ?-developments and finite automata.- A generalization of automatic sequences.- Word problems over traces which are solvable in linear time.- Computing minimum spanning forests on 1- and 2-dimensional processor arrays.- Parallel computation of discrete Voronoi diagrams.- Successive approximation in parallel graph algorithms.- Reversals and alternation.- On the power of parity polynomial time.- Complete problems and strong polynomial reducibilities.- If deterministic and nondeterministic space complexities are equal for log log n then they are also equal for log n.- On the complexity of approximating the independent set problem.- Average number of messages for distributed leader finding in rings of processors.- Time vs bits.- Distributed computing on transitive networks: The torus.- Time is not a healer.- Area efficient methods to increase the reliability of combinatorial circuits.- Fault masking probabilities with single and multiple signature analysis.- Chain properties of rule closures.- It is undecidable whether the Knuth-Bendix completion procedure generates a crossed pair.- Algebraic specifications for domain theory.- The query topology in logic programming.- Testing membership: Beyond permutation groups.- Membership in polynomial ideals over Q is exponential space complete.- Some complexity theoretic aspects of AC rewriting.- Deciding bisimulation equivalences for a class of non-finite-state programs.- Measure of parallelism of distributed computations.- Decidability of weak fairness in petri nets.- New results on the generalized star-height problem.- On the equivalence problem for deterministic multitape automata and transducers.- Deciding equivalence of finite tree automata.- Concatenable segment trees.- Shortest edge-disjoint paths in graphs.- Rounds versus time for the two person pebble game.- AXE: the syntax driven diagram editor for visual languages used in the software engineering environments AxIS.- GraphEd: An interactive graph editor.- SAMPLE a language dependent prototyping environment.- Examining the satisfiability of the formulas of Propositional Dynamic Logic.- Amore: A system for computing automata, MOnoids, and regular expressions.- A proof system for type theory and CCS.- Implementation of a transition semantics for parallel programs with shared variables.