STACS 88: 5th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 11-13,1988; Proceedings / Edition 1

by Robert Cori, Martin Wirsing

Overview

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.

Product Details

ISBN-13:	9783540188346
Publisher:	Springer Berlin Heidelberg
Publication date:	02/22/1988
Series:	Lecture Notes in Computer Science , #294
Edition description:	1988
Pages:	408
Product dimensions:	8.50(w) x 10.98(h) x 0.03(d)

Table of Contents

Geometry of numbers and integer programming.- Getting back to the past in the union-find problem.- On the construction of optimal time adders.- On computations with integer division.- Maintaining range trees in secondary memory.- Solving parametric problems on trees.- On the k-colouring of circle-graphs.- Functional equations for data structures.- The power of polynomial size—-branching programs.- Collapsing oracle hierarchies, census functions and logarithmically many queries.- Domino games with an application to the complexity of boolean algebras with bounded quantifier alternations.- An automatic speed-up of random access machines with powerful arithmetic instructions.- Characterizing the polynomial Hierarchy by alternating auxiliary pushdown automata.- Hotz-isomorphism theorems in formal language theory.- First-order properties of trees, star-free expressions, and aperiodicity.- Cyclic rational transductions and polynomials of rational functions.- Construction of a family of finite maximal codes.- Fonctions Generatrices Transcendantes a Coefficients Engendres par Automates.- The relation of two patterns with comparable languages.- Hierarchical contextual rewriting with several levels.- Generalized bisimulation in relational specifications.- On polynomial time graph grammars.- An axiomatic definition of context-free rewriting and its application to NLC graph grammars.- Efficient distributed algorithms by using the archimedean time assumption.- A simple prool for secure circuit evaluation.- Scheduling independent jobs on hypercubes.- Voronoi diagrams based on general metrics in the plane.- Geometric containment, common roots of polynomials and partial orders.- Extension of the notion of map and subdivisions of a three-dimensional space.- An optimal algorithm fordetecting weak visibility of a polygon.- Polygon placement under translation and rotation.- On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages.- On morphisms of trace monoids.- An automaton characterization of fairness in SCCS.- A compositional semantics for Concurrent Prolog.- Functions and relations: The graal system.- LPC: A concurrent programming laboratory.- Darwin: Computer algebra and enumerative combinatorics.- Some tools for an inference laboratory (ATINF).- Modulog and the Modula workstation.- The granules, glutton: An idea, an algorithm to implement on multiprocessor.- Prototype de Venus: Un Outil d'Aide a la Verification de Systemes Communicantes.- PLEXUS: A system for implementing hierarchical graph algorithms.