
STACS 87
4th Annual Symposium on Theoretical Aspects of Computer Science, Passau, FRG, February 19-21, 1987
Springer (Publisher)
Published on 11. February 1987
Book
Paperback/Softback
XII, 483 pages
978-3-540-17219-2 (ISBN)
Description
Towards a theory of relativizations: Positive relativizations.- Natural semantics.- On local routing of two-terminal nets.- Geometric relations among Voronoi diagrams.- Finding the largest empty rectangle on a grated surface.- Efficient graph algorithms using limited communication on a fixed-size array of processors.- On selecting the largest element in spite of erroneous information.- The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems.- Graph isomorphism is in the low hierarchy.- A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees.- Self-reducibility.- Probability one separation of the Boolean hierarchy.- Reversal complexity of multicounter and multihead machines.- Computing the counting function of context-free languages.- On the k-freeness of morphisms on free monoids.- Avoidable patterns on 2 letters.- Polynomial operations on rational languages.- Some structural aspects of hypergraph languages generated by hyperedge replacement.- Specification and implementation of concurrently accessed data structures: An abstract data type approach.- On implementations of loose abstract data type specifications and their vertical composition.- Are homomorphisms sufficient for behavioural implementations of deterministic and nondeterministic data types?.- Some remarks on presentations by finite Church-Rosser Thue systems.- Ground term confluence in parametric conditional equational specifications.- Describing semantic domains with sprouts.- Comparing direct and continuation semantics styles for concurrent languages.- Expressibility of first order logic with a nondeterministic inductive operator.- Bounded nondeterminism and the approximation induction principle in processalgebra.- The step failure semantics.- On the complexity of containment, equivalence, and reachability for finite and 2-dimensional vector addition systems with states.- Closure properties of deterministic Petri nets.- Some results on fairness: The regular case.- Decidability questions for fairness in Petri nets.- Optimal sorting on multi-dimensionally mesh-connected computers.- On the contact-minimization-problem.- Making distributed spanning tree algorithms fault-resilient.- The derivation of on-the-fly garbage collection algorithms from distributed termination detection protocols.- On the expected complexity of distributed selection.- LPG: A generic, logic and functional programming language.- CEC.- ASSPEGIQUE.- REVEUR4 : A laboratory for conditional rewriting.- An interactive, incremental and portable computer algebra system for ?-calculus and combinatory logic based on video edition and rewriting techniques.- The Passau RAP System: Rapid prototyping for algebraic specifications.- SPRAC: A software engineering environment.- SLOG: A logic interpreter for equational clauses.- An algebraic transformation system for occam programs.- REVE a rewrite rule laboratory.
More details
Series
Edition
1987 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
XII, 483 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 27 mm
Weight
750 gr
ISBN-13
978-3-540-17219-2 (9783540172192)
DOI
10.1007/BFb0039590
Schweitzer Classification
Content
Towards a theory of relativizations: Positive relativizations.- Natural semantics.- On local routing of two-terminal nets.- Geometric relations among Voronoi diagrams.- Finding the largest empty rectangle on a grated surface.- Efficient graph algorithms using limited communication on a fixed-size array of processors.- On selecting the largest element in spite of erroneous information.- The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems.- Graph isomorphism is in the low hierarchy.- A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees.- Self-reducibility.- Probability one separation of the Boolean hierarchy.- Reversal complexity of multicounter and multihead machines.- Computing the counting function of context-free languages.- On the k-freeness of morphisms on free monoids.- Avoidable patterns on 2 letters.- Polynomial operations on rational languages.- Some structural aspects of hypergraph languages generated by hyperedge replacement.- Specification and implementation of concurrently accessed data structures: An abstract data type approach.- On implementations of loose abstract data type specifications and their vertical composition.- Are homomorphisms sufficient for behavioural implementations of deterministic and nondeterministic data types?.- Some remarks on presentations by finite Church-Rosser Thue systems.- Ground term confluence in parametric conditional equational specifications.- Describing semantic domains with sprouts.- Comparing direct and continuation semantics styles for concurrent languages.- Expressibility of first order logic with a nondeterministic inductive operator.- Bounded nondeterminism and the approximation induction principle in processalgebra.- The step failure semantics.- On the complexity of containment, equivalence, and reachability for finite and 2-dimensional vector addition systems with states.- Closure properties of deterministic Petri nets.- Some results on fairness: The regular case.- Decidability questions for fairness in Petri nets.- Optimal sorting on multi-dimensionally mesh-connected computers.- On the contact-minimization-problem.- Making distributed spanning tree algorithms fault-resilient.- The derivation of on-the-fly garbage collection algorithms from distributed termination detection protocols.- On the expected complexity of distributed selection.- LPG: A generic, logic and functional programming language.- CEC.- ASSPEGIQUE.- REVEUR4 : A laboratory for conditional rewriting.- An interactive, incremental and portable computer algebra system for ?-calculus and combinatory logic based on video edition and rewriting techniques.- The Passau RAP System: Rapid prototyping for algebraic specifications.- SPRAC: A software engineering environment.- SLOG: A logic interpreter for equational clauses.- An algebraic transformation system for occam programs.- REVE a rewrite rule laboratory.