Advances in Algorithms, Languages, and Complexity

1. Front Matter

   Pages i-xxxiv

   PDF

2. Theorem Proving in Hierarchical Clausal Specifications

   • J. Avenhaus, K. Madlener

   Pages 1-51

3. Algorithms for Learning Finite Automata from Queries: A Unified View

   • José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe

   Pages 53-72

4. Coding Complexity: The Computational Complexity of Succinct Descriptions

   • José L. Balcázar, Ricard Gavaldà, Osamu Watanabe

   Pages 73-91

5. Homomorphic Representations of Certain Classes of Languages

   • Franz J. Brandenburg

   Pages 93-110

6. Block-Synchronization Context-Free Grammars

   • Helmut Jürgensen, Kai Salomaa

   Pages 111-137

7. High Sets for NP

   • Johannes Köbler, Uwe Schöning

   Pages 139-156

8. Average-Case Analysis Using Kolmogorov Complexity

   • Ming Li, Paul Vitányi

   Pages 157-169

9. Genericity and Randomness over Feasible Probability Measures

   • Amy K. Lorentz, Jack H. Lutz

   Pages 171-187

10. Book’s Impact on the Theory of Thue Systems — Abstract

    • Robert McNaughton

    Pages 189-190

11. Sparse Hard Sets for P

    • Dieter van Melkebeek, Mitsunori Ogihara

    Pages 191-208

12. A Survey of Continuous-Time Computation Theory

    • Pekka Orponen

    Pages 209-224

13. Properties of Monoids That Are Presented by Finite Convergent String-Rewriting Systems — A Survey

    • F. Otto, Y. Kobayashi

    Pages 225-266

14. Relaxed Balancing in Search Trees

    • Eljas Soisalon-Soininen, Peter Widmayer

    Pages 267-283

15. Measure One Results in Computational Complexity Theory

    • Heribert Vollmer, Klaus W. Wagner

    Pages 285-312

16. Average-Case Intractable NP Problems

    • Jie Wang

    Pages 313-378

17. Multichannel Lightwave Networks

    • Peng-Jun Wan, Feng Cao

    Pages 379-396

This book contains a collection of survey papers in the areas of algorithms, lan­ guages and complexity, the three areas in which Professor Ronald V. Book has made significant contributions. As a fonner student and a co-author who have been influenced by him directly, we would like to dedicate this book to Professor Ronald V. Book to honor and celebrate his sixtieth birthday. Professor Book initiated his brilliant academic career in 1958, graduating from Grinnell College with a Bachelor of Arts degree. He obtained a Master of Arts in Teaching degree in 1960 and a Master of Arts degree in 1964 both from Wesleyan University, and a Doctor of Philosophy degree from Harvard University in 1969, under the guidance of Professor Sheila A. Greibach. Professor Book's research in discrete mathematics and theoretical com­ puter science is reflected in more than 150 scientific publications. These works have made a strong impact on the development of several areas of theoretical computer science. A more detailed summary of his scientific research appears in this volume separately.

• algorithms
• automata
• complexity
• complexity theory
• computation
• computational complexity
• computer science
• grammars
• Kolmogorov complexity
• mathematics
• Monoid
• network
• randomness
• theorem proving
• theoretical computer science

• University of Minnesota, USA

  Ding-Zhu Du

• State University of New York, Stony Brook, USA

  Ker-I Ko

Policies and ethics