STACS 88

1. Front Matter

   PDF

2. Geometry of numbers and integer programming

   • C. P. Schnorr

   Pages 1-7

3. Getting back to the past in the union-find problem

   • Giorgio Gambosi, Giuseppe F. Italiano, Maurizio Talamo

   Pages 8-17

4. On the construction of optimal time adders

   • Bernd Becker, Reiner Kolla

   Pages 18-28

5. On computations with integer division

   • Bettina Just, Fb Mathematik, Friedhelm Meyer auf der Heide, Fb Informatik, Avi Wigderson

   Pages 29-37

6. Maintaining range trees in secondary memory

   • Mark H. Overmars, Michiel H. M. Smid

   Pages 38-51

7. Solving parametric problems on trees

   • David Fernández-Baca, Giora Slutzki

   Pages 52-60

8. On the k-colouring of circle-graphs

   • Walter Unger

   Pages 61-72

9. Functional equations for data structures

   • François Bergeron, Gilbert Labelle, Pierre Leroux

   Pages 73-80

10. The power of polynomial size Ω-branching programs

    • Christoph Meinel

    Pages 81-90

11. Collapsing oracle hierarchies, census functions and logarithmically many queries

    • Uwe Schöning, Klaus W. Wagner

    Pages 91-97

12. Domino games with an application to the complexity of boolean algebras with bounded quantifier alternations

    • Erich Grädel

    Pages 98-107

13. An automatic speed-up of random access machines with powerful arithmetic instructions

    • Ingolf Wald

    Pages 108-117

14. Characterizing the polynomial Hierarchy by alternating auxiliary pushdown automata

    • Birgit Jenner, Bernd Kirsig

    Pages 118-125

15. Hotz-isomorphism theorems in formal language theory

    • Volker Diekert, Axel Möbus

    Pages 126-135

16. First-order properties of trees, star-free expressions, and aperiodicity

    • Uschi Heuter

    Pages 136-148

17. Cyclic rational transductions and polynomials of rational functions

    • Alain Terlutte

    Pages 149-158

18. Construction of a family of finite maximal codes

    • Clelia De Felice

    Pages 159-169

19. Fonctions Generatrices Transcendantes a Coefficients Engendres par Automates

    • Jean-Paul Allouche, Bernard Rande, Loÿs Thimonier

    Pages 170-183

20. The relation of two patterns with comparable languages

    • Gilberto Filè

    Pages 184-192

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.

• Algorithms
• Automat
• Bisimulation
• Boolean algebra
• Modula
• Monoid
• Scheduling
• automata
• complexity
• computer
• computer algebra
• data structure
• formal language
• programming
• semantics
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics