STACS 88: 5th Annual Symposium on Theoretical Aspects of Computer Science Bordeaux, France, February 11–13, 1988 Proceedings

C. P. Schnorr (auth.), Robert Cori, Martin Wirsing (eds.)3540188347, 9783540188346

This volume contains the presentations of the Fifth Symposium on Theoretical Aspects of Computer Science (STACS 88) held at the University of Bordeaux, February 11-13, 1988. 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: algorithms, complexity, formal languages, rewriting systems and abstract data types, graph grammars, distributed algorithms, geometrical algorithms, trace languages, semantics of parallelism.

---

Table of contents :
Geometry of numbers and integer programming….Pages 1-7
Getting back to the past in the union-find problem….Pages 8-17
On the construction of optimal time adders….Pages 18-28
On computations with integer division….Pages 29-37
Maintaining range trees in secondary memory….Pages 38-51
Solving parametric problems on trees….Pages 52-60
On the k-colouring of circle-graphs….Pages 61-72
Functional equations for data structures….Pages 73-80
The power of polynomial size Ω-branching programs….Pages 81-90
Collapsing oracle hierarchies, census functions and logarithmically many queries….Pages 91-97
Domino games with an application to the complexity of boolean algebras with bounded quantifier alternations….Pages 98-107
An automatic speed-up of random access machines with powerful arithmetic instructions….Pages 108-117
Characterizing the polynomial Hierarchy by alternating auxiliary pushdown automata….Pages 118-125
Hotz-isomorphism theorems in formal language theory….Pages 126-135
First-order properties of trees, star-free expressions, and aperiodicity….Pages 136-148
Cyclic rational transductions and polynomials of rational functions….Pages 149-158
Construction of a family of finite maximal codes….Pages 159-169
Fonctions Generatrices Transcendantes a Coefficients Engendres par Automates….Pages 170-183
The relation of two patterns with comparable languages….Pages 184-192
Hierarchical contextual rewriting with several levels….Pages 193-206
Generalized bisimulation in relational specifications….Pages 207-226
On polynomial time graph grammars….Pages 227-236
An axiomatic definition of context-free rewriting and its application to NLC graph grammars….Pages 237-247
Efficient distributed algorithms by using the archimedean time assumption….Pages 248-263
A simple protocol for secure circuit evaluation….Pages 264-272
Scheduling independent jobs on hypercubes….Pages 273-280
Voronoi diagrams based on general metrics in the plane….Pages 281-291
Geometric containment, common roots of polynomials and partial orders….Pages 292-300
Extension of the notion of map and subdivisions of a three-dimensional space….Pages 301-311
An optimal algorithm for detecting weak visibility of a polygon….Pages 312-321
Polygon placement under translation and rotation….Pages 322-333
On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages….Pages 334-345
On morphisms of trace monoids….Pages 346-355
An automaton characterization of fairness in SCCS….Pages 356-372
A compositional semantics for Concurrent Prolog….Pages 373-388
Functions and relations: The graal system….Pages 389-390
LPC: A concurrent programming laboratory….Pages 391-392
Darwin: Computer algebra and enumerative combinatorics….Pages 393-394
Some tools for an inference laboratory (ATINF)….Pages 395-396
Modulog and the Modula workstation….Pages 397-398
The granules, glutton: An idea, an algorithm to implement on multiprocessor….Pages 399-400
Prototype de Venus: Un Outil d’Aide a la Verification de Systemes Communicantes….Pages 401-402
PLEXUS: A system for implementing hierarchical graph algorithms….Pages 403-404