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

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