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

Friedhelm Meyer auf der Heide (auth.), B. Monien, R. Cori (eds.)3540508406, 9783540508403

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.

---

Table of contents :
On genuinely time bounded computations….Pages 1-16
Unified Algebras and action semantics….Pages 17-35
Properties of infinite words : Recent results….Pages 36-46
A first order logic for partial functions….Pages 47-58
Observational implementations….Pages 59-71
On the boundary of a union of Rays….Pages 72-83
Dynamic planar point location with optimal query time….Pages 84-95
An O(n log n) algorithm for computing a link center in a simple polygon….Pages 96-107
Polynomial graph-colorings….Pages 108-119
Time-optimal simulations of networks by universal parallel computers….Pages 120-131
Classes of picture languages that cannot be distinguished in the chain code concept and deletion of redundant retreats….Pages 132-143
Linear numeration systems, θ-developments and finite automata….Pages 144-155
A generalization of automatic sequences….Pages 156-167
Word problems over traces which are solvable in linear time….Pages 168-180
Computing minimum spanning forests on 1- and 2-dimensional processor arrays….Pages 181-192
Parallel computation of discrete Voronoi diagrams….Pages 193-204
Successive approximation in parallel graph algorithms….Pages 205-217
Reversals and alternation….Pages 218-228
On the power of parity polynomial time….Pages 229-239
Complete problems and strong polynomial reducibilities….Pages 240-250
If deterministic and nondeterministic space complexities are equal for log log n then they are also equal for log n ….Pages 251-255
On the complexity of approximating the independent set problem….Pages 256-268
Average number of messages for distributed leader finding in rings of processors….Pages 269-281
Time vs bits….Pages 282-293
Distributed computing on transitive networks: The torus….Pages 294-303
Time is not a healer….Pages 304-313
Area efficient methods to increase the reliability of combinatorial circuits….Pages 314-326
Fault masking probabilities with single and multiple signature analysis….Pages 327-338
Chain properties of rule closures….Pages 339-347
It is undecidable whether the Knuth-Bendix completion procedure generates a crossed pair….Pages 348-359
Algebraic specifications for domain theory….Pages 360-374
The query topology in logic programming….Pages 375-387
Testing membership: Beyond permutation groups….Pages 388-399
Membership in polynomial ideals over Q is exponential space complete….Pages 400-406
Some complexity theoretic aspects of AC rewriting….Pages 407-420
Deciding bisimulation equivalences for a class of non-finite-state programs….Pages 421-433
Measure of parallelism of distributed computations….Pages 434-445
Decidability of weak fairness in petri nets….Pages 446-457
New results on the generalized star-height problem….Pages 458-467
On the equivalence problem for deterministic multitape automata and transducers….Pages 468-479
Deciding equivalence of finite tree automata….Pages 480-492
Concatenable segment trees….Pages 493-504
Shortest edge-disjoint paths in graphs….Pages 505-516
Rounds versus time for the two person pebble game….Pages 517-529
AXE: the syntax driven diagram editor for visual languages used in the software engineering environments AxIS….Pages 530-531
Graph Ed : An interactive graph editor….Pages 532-533
SAMPLE a language dependent prototyping environment….Pages 534-535
Examining the satisfiability of the formulas of Propositional Dynamic Logic….Pages 536-536
Amore: A system for computing automata, MOnoids, and regular expressions….Pages 537-538
A proof system for type theory and CCS….Pages 539-540
Implementation of a transition semantics for parallel programs with shared variables….Pages 541-543