STACS 92

1. Front Matter

   PDF

2. Structuring and modularizing algebraic specifications: the PLUSS specification language, evolutions and perspectives

   • Marie-Claude Gaudel

   Pages 1-18

3. The parallel complexity of tree embedding problems (extended abstract)

   • Arvind Gupta, Naomi Nishimura

   Pages 19-32

4. A theory of strict P-completeness

   • Anne Condon

   Pages 33-44

5. Fast and optimal simulations between CRCW PRAMs

   • Torben Hagerup

   Pages 45-56

6. Suitability of the propositional temporal logic to express properties of real-time systems

   • Eric Nassor, Guy Vidal-Naquet

   Pages 57-70

7. Axiomatizations of backtracking

   • Michel Billaud

   Pages 71-82

8. Joining k- and l-recognizable sets of natural numbers

   • Roger Villemaire

   Pages 83-94

9. On the performance of networks with multiple busses

   • Friedhelm Meyer auf der Heide, Hieu Thien Pham

   Pages 95-108

10. Efficient algorithms for solving systems of linear equations and path problems

    • Venkatesh Radhakrishnan, Harry B. Hunt III, Richard E. Stearns

    Pages 109-119

11. Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition

    • Lawrence L. Larmore, Wojciech Rytter

    Pages 121-132

12. A simplified technique for hidden-line elimination in terrains

    • Franco P. Preparata, Jeffrey Scott Vitter

    Pages 133-146

13. A competitive analysis of nearest neighbor based algorithms for searching unknown scenes

    • Bala Kalyanasundaram, Kirk Pruhs

    Pages 147-157

14. Equality and disequality constraints on direct subterms in tree automata

    • Bogaert B., Tison S.

    Pages 159-171

15. Deterministic regular languages

    • Anne Brüggemann-Klein, Derick Wood

    Pages 173-184

16. The extended low hierarchy is an infinite hierarchy

    • Ming-Jye Sheu, Timothy Juris Long

    Pages 185-198

17. Locally definable acceptance types for polynomial time machines

    • Ulrich Hertrampf

    Pages 199-207

18. The theory of the polynomial many-one degrees of recursive sets is undecidable

    • Klaus Ambos-Spies, André Nies

    Pages 209-218

19. A plane-sweep algorithm for finding a closest pair among convex planar objects

    • Frank Bartling, Klaus Hinrichs

    Pages 219-232

20. Linear approximation of simple objects

    • Jean-Marc Robert, Godfried Toussaint

    Pages 233-244

This volume gives the proceedings of the ninth Symposium on Theoretical Aspects of Computer Science (STACS). This annual symposium is held alternately in France and Germany and is organized jointly by the Special Interest Group for Fundamental Computer Science of the Association Francaise des Sciences et Technologies de l'Information et des Syst mes (AFCET) and the Special Interest Group for Theoretical Computer Science of the Gesellschaft f}r Informatik (GI). The volume includes three invited lectures and sections on parallel algorithms, logic and semantics, computational geometry, automata and languages, structural complexity, computational geometry and learning theory, complexity and communication, distributed systems, complexity, algorithms, cryptography, VLSI, words and rewriting, and systems.

• Automat
• algorithm
• algorithms
• automata
• complexity
• computational geometry
• computer
• computer science
• distributed systems
• logic
• semantics
• algorithm analysis and problem complexity

Policies and ethics