Ebook: STACS 87: 4th Annual Symposium on Theoretical Aspects of Computer Science Passau, Federal Republic of Germany, February 19–21, 1987 Proceedings

---

Content:
Front Matter....Pages -
Towards a theory of relativizations: Positive relativizations....Pages 1-21
Natural semantics....Pages 22-39
On local routing of two-terminal nets....Pages 40-52
Geometric relations among Voronoi diagrams....Pages 53-65
Finding the largest empty rectangle on a grated surface....Pages 66-75
Efficient graph algorithms using limited communication on a fixed-size array of processors....Pages 76-87
On selecting the largest element in spite of erroneous information....Pages 88-99
The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems....Pages 100-113
Graph isomorphism is in the low hierarchy....Pages 114-124
A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees....Pages 125-135
Self-reducibility....Pages 136-147
Probability one separation of the Boolean hierarchy....Pages 148-158
Reversal complexity of multicounter and multihead machines....Pages 159-168
Computing the counting function of context-free languages....Pages 169-179
On the k-freeness of morphisms on free monoids....Pages 180-188
Avoidable patterns on 2 letters....Pages 189-197
Polynomial operations on rational languages....Pages 198-206
Some structural aspects of hypergraph languages generated by hyperedge replacement....Pages 207-219
Specification and implementation of concurrently accessed data structures: An abstract data type approach....Pages 220-244
On implementations of loose abstract data type specifications and their vertical composition....Pages 245-259
Are homomorphisms sufficient for behavioural implementations of deterministic and nondeterministic data types?....Pages 260-271
Some remarks on presentations by finite Church-Rosser Thue systems....Pages 272-285
Ground term confluence in parametric conditional equational specifications....Pages 286-298
Describing semantic domains with sprouts....Pages 299-310
Comparing direct and continuation semantics styles for concurrent languages....Pages 311-322
Expressibility of first order logic with a nondeterministic inductive operator....Pages 323-335
Bounded nondeterminism and the approximation induction principle in process algebra....Pages 336-347
The step failure semantics....Pages 348-359
On the complexity of containment, equivalence, and reachability for finite and 2-dimensional vector addition systems with states....Pages 360-370
Closure properties of deterministic Petri nets....Pages 371-382
Some results on fairness: The regular case....Pages 383-395
Decidability questions for fairness in Petri nets....Pages 396-407
Optimal sorting on multi-dimensionally mesh-connected computers....Pages 408-419
On the contact-minimization-problem....Pages 420-431
Making distributed spanning tree algorithms fault-resilient....Pages 432-444
The derivation of on-the-fly garbage collection algorithms from distributed termination detection protocols....Pages 445-455
On the expected complexity of distributed selection....Pages 456-467
LPG: A generic, logic and functional programming language....Pages 468-469
CEC....Pages 470-470
ASSPEGIQUE....Pages 471-471
REVEUR4 : A laboratory for conditional rewriting....Pages 472-473
An interactive, incremental and portable computer algebra system for ?-calculus and combinatory logic based on video edition and rewriting techniques....Pages 474-474
The Passau RAP System: Rapid prototyping for algebraic specifications....Pages 475-476
SPRAC: A software engineering environment....Pages 477-478
SLOG: A logic interpreter for equational clauses....Pages 479-480
An algebraic transformation system for occam programs....Pages 481-481
REVE a rewrite rule laboratory....Pages 482-483
Back Matter....Pages -

---

Content:
Front Matter....Pages -
Towards a theory of relativizations: Positive relativizations....Pages 1-21
Natural semantics....Pages 22-39
On local routing of two-terminal nets....Pages 40-52
Geometric relations among Voronoi diagrams....Pages 53-65
Finding the largest empty rectangle on a grated surface....Pages 66-75
Efficient graph algorithms using limited communication on a fixed-size array of processors....Pages 76-87
On selecting the largest element in spite of erroneous information....Pages 88-99
The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems....Pages 100-113
Graph isomorphism is in the low hierarchy....Pages 114-124
A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees....Pages 125-135
Self-reducibility....Pages 136-147
Probability one separation of the Boolean hierarchy....Pages 148-158
Reversal complexity of multicounter and multihead machines....Pages 159-168
Computing the counting function of context-free languages....Pages 169-179
On the k-freeness of morphisms on free monoids....Pages 180-188
Avoidable patterns on 2 letters....Pages 189-197
Polynomial operations on rational languages....Pages 198-206
Some structural aspects of hypergraph languages generated by hyperedge replacement....Pages 207-219
Specification and implementation of concurrently accessed data structures: An abstract data type approach....Pages 220-244
On implementations of loose abstract data type specifications and their vertical composition....Pages 245-259
Are homomorphisms sufficient for behavioural implementations of deterministic and nondeterministic data types?....Pages 260-271
Some remarks on presentations by finite Church-Rosser Thue systems....Pages 272-285
Ground term confluence in parametric conditional equational specifications....Pages 286-298
Describing semantic domains with sprouts....Pages 299-310
Comparing direct and continuation semantics styles for concurrent languages....Pages 311-322
Expressibility of first order logic with a nondeterministic inductive operator....Pages 323-335
Bounded nondeterminism and the approximation induction principle in process algebra....Pages 336-347
The step failure semantics....Pages 348-359
On the complexity of containment, equivalence, and reachability for finite and 2-dimensional vector addition systems with states....Pages 360-370
Closure properties of deterministic Petri nets....Pages 371-382
Some results on fairness: The regular case....Pages 383-395
Decidability questions for fairness in Petri nets....Pages 396-407
Optimal sorting on multi-dimensionally mesh-connected computers....Pages 408-419
On the contact-minimization-problem....Pages 420-431
Making distributed spanning tree algorithms fault-resilient....Pages 432-444
The derivation of on-the-fly garbage collection algorithms from distributed termination detection protocols....Pages 445-455
On the expected complexity of distributed selection....Pages 456-467
LPG: A generic, logic and functional programming language....Pages 468-469
CEC....Pages 470-470
ASSPEGIQUE....Pages 471-471
REVEUR4 : A laboratory for conditional rewriting....Pages 472-473
An interactive, incremental and portable computer algebra system for ?-calculus and combinatory logic based on video edition and rewriting techniques....Pages 474-474
The Passau RAP System: Rapid prototyping for algebraic specifications....Pages 475-476
SPRAC: A software engineering environment....Pages 477-478
SLOG: A logic interpreter for equational clauses....Pages 479-480
An algebraic transformation system for occam programs....Pages 481-481
REVE a rewrite rule laboratory....Pages 482-483
Back Matter....Pages -
....