Mathematical Foundations of Computer Science 1992

1. Front Matter

   PDF

2. On range searching with semialgebraic sets

   • Pankaj K. Agarwal, Jiří Matoušek

   Pages 1-13

3. Graph layout problems

   • J. Díaz

   Pages 14-23

4. Parallel recognition and ranking of context-free languages

   • Klaus-Jörn Lange, Peter Rossmanith, Wojciech Rytter

   Pages 24-36

5. On the expansion of combinatorial polytopes

   • Milena Mihail

   Pages 37-49

6. Neural networks and complexity theory

   • Pekka Orponen

   Pages 50-61

7. Theory of computation over stream algebras, and its applications

   • J. V. Tucker, J. I. Zucker

   Pages 62-80

8. Methods in parallel algorithmcs

   • Uzi Vishkin

   Pages 81-81

9. On the complexity of small description and related topics

   • Osamu Watanabe

   Pages 82-94

10. Weak parallel machines: A new class of physically feasible parallel machine models

    • Juraj Wiedermann

    Pages 95-111

11. The complexity of graph connectivity

    • Avi Wigderson

    Pages 112-132

12. A perfect parallel dictionary

    • Holger Bast, Martin Dietzfelbinger, Torben Hagerup

    Pages 133-141

13. Some remarks on the test complexity of iterative logic arrays

    • Bernd Becker, Joachim Hartmann

    Pages 142-152

14. The degree structure of 1-L reductions

    • Hans-Jörg Burtschick, Albrecht Hoene

    Pages 153-161

15. Promise problems and access to unambiguous computation

    • Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoč

    Pages 162-171

16. On the complexity of incremental computation

    • Suresh Chari, Desh Ranjan, Pankaj Rohatgi

    Pages 172-180

17. Rational transductions and complexity of counting problems

    • Christian Choffrut, Massimiliano Goldwurm

    Pages 181-190

18. Negation elimination in equational formulae

    • Hubert Comon, Maribel Fernández

    Pages 191-199

19. Object interaction

    • J. F. Costa, A. Sernadas, C. Sernadas, H. -D. Ehrich

    Pages 200-208

20. Strong normalization of substitutions

    • P. -L. Curien, T. Hardin, A. Ríos

    Pages 209-217

This volume contains 10 invited papers and 40 short communications contributed for presentation at the 17th Symposium on Mathematical Foundations of Computer Science, held in Prague, Czechoslovakia, August 24-28, 1992. The series of MFCS symposia, organized alternately in Poland and Czechoslovakia since 1972, has a long and well established tradition. The purpose of the series is to encourage high-quality research in all branches of theoretical computer science and to bring together specialists working actively in the area. Numerous topics are covered in this volume. The invited papers cover: range searching with semialgebraic sets, graph layout problems, parallel recognition and ranking of context-free languages, expansion of combinatorial polytopes, neural networks and complexity theory, theory of computation over stream algebras, methods in parallel algorithms, the complexity of small descriptions, weak parallel machines, and the complexity of graph connectivity.

• Datenstrukturen
• Komplexität
• Nebenläufigkeit
• Parallelität
• Semantik
• Text
• algorithms
• complexity
• concurrency
• data structures
• logic
• parallelism
• semantics
• sets
• theoretical computer science
• algorithm analysis and problem complexity

Policies and ethics